Robot Teams for Multi-Objective Tasks

Artificial Intelligence research has developed, during the last fifty years, a large variety of tools aimed at establishing rational behaviors for cognitive entities, called agents. This dissertation addresses the problem of producing rational behaviors for a team of agents pursuing possibly different objectives. The problem can be decomposed into the following two research issues: i) multi-agent behavior and execution modelling, and, ii) multi-objective problem solving. Our resarch focus on multi-agent systems has been modelling distributed execution of asynchronous plans composed of actions of uncertain duration, possibly coordinated through direct communication. The distributed execution and the communication costs require to model the dynamics of knowledge when asynchronously distributed in the system under the effect of local and communication actions. The second research focus of this thesis, has been multi-objective problem solving. The introduction of multiple objectives in planning domains, allows us to generalize classical multi-agent planning, thus augmenting the class of solvable problems. Multi-objective formulations allow an incomplete, and possibly contradictory, description of goals, and are frequent in many practical applications. For example, consider the case where requests to a system come from a large community of users or from the members of a research group studying different aspects of a complex problem. This thesis provides three main contributions. The first contribution consists of two formal tools for modelling multi-agent systems. One, for planning, and, one, for distributed execution. Each model defines a class of languages based on single-agent action languages and Petri nets, respectively. The second contribution addresses two multi-objective issues: solution concept and solving techniques. First, we define a novel solution concept which is, to our knowledge, the first refinement of Pareto optimality for any multi-objective problem. Second, we provide a sound and complete algorithm for solving it. Finally, the third contribution is a case study on the Urban Search And Rescue (USAR) robotic problem, presented in three formulations of increasing complexity. USAR, in its classical formulation, is a multi-objective problem where the objectives are: exploration, mapping, and victim detection.