Collaborative Missions with Heterogeneous Networked Teams

You are cordially invited to attend the PhD Dissertation Defense of Eduardo FEO FLUSHING on Wednesday, December 13th 2017 at 16h30 in room CC-250 (Main building)

Abstract:

This thesis addresses the problem of mission planning in teams of collaborative autonomous agents. The teams that we consider feature physical agents (e.g., robots, humans, animals) and are heterogeneous. Moreover, the agents are networked, meaning that the agents in the team share a common communication network (possibly ad hoc). These team characteristics are selected having in mind target real-world applications such as search and rescue, environmental monitoring, and patrolling, that all require, or can take profit of a multi-agent team offering a diversity of cognitive and sensory-motor skills, a potential redundancy of resources, parallelism, and spatial distribution.

In order to get the best out of the team for the sake of the mission, especially in terms of creating internal synergies, effective coordination and cooperation schemes need to be in place. This is precisely the focus of this thesis, that considers a generic mission planning level that breaks down into three sub-problems that are addressed jointly: task allocation, task scheduling, and path routing. We assume that a generic mission for the team is defined through a set of given spatially distributed tasks (e.g., search for survivors in the third floor of the building, monitor a specific patch of the environment) and by a limited time budget. Therefore, task allocation deals with assigning sub-set of tasks to the agents by optimizing the matching with their skills. Task scheduling defines how much time an agent should spend on each task, depending on task service requirements and on the total time budget.  Finally, given the assumed spatially distributed nature of the tasks, path routing defines the sequence of execution of each sub-set of tasks assigned to an agent and the routes the agents use to travel from one task to the other, addressing at the same time proximity issues among the agents, such as supporting communications and local collaborations, or minimizing  mutual interference. In the thesis, an operational model for mission planning is defined and formalized as a mixed integer linear program (MILP).  The formulation is extremely versatile and addresses the challenges of team heterogeneity, collaborative efforts, communications, mutual interactions and dependencies between the agents, deviations between task execution and issued plans.

In order to cope with the computational challenges that are usually associated with solving a potentially large MILP, and therefore support scalability of performance, a matheuristic approach is proposed to efficiently obtain solutions. The approach combines an exact solver and metaheuristics, resulting in an anytime algorithm with performance guarantees.  Moreover, in the direction of supporting scalability, a decentralized computational model is defined in a top-down manner from the main MILP model, that drastically reduces computational requirements without incurring into a major decrease in performance.

Given the importance of communications in a distributed team (e.g., communication to and from a control center, or within the team), model for connectivity-aware planning, as well as for the simultaneous solution of planning, scheduling and data routing are proposed as extensions of the core MILP formulation.

Based on the envisaged application scenarios, an original model for team rostering is also proposed, with the aim of supporting long-lasting missions that involve and require work shifts among the agents.

All the mentioned models have been analyzed and evaluated in a number simulation and computational experiments that show both good scalability of computations and efficacy of the expected team performance.

Finally, a particular attention has been devoted to the application of the developed models in search and rescue scenarios. At this aim, an integrated mission support system has been developed, that contains a simulator, allows to issue and track a mission in real time, and exploits GIS data to compute a mission plan and profile the agents.

Dissertation Committee:

• Prof. Luca Maria Gambardella, IDSIA, Switzerland (Research Advisor)
• Prof. Gianni A. Di Caro, Carnegie Mellon University, USA (Research co-Advisor)
• Prof. Cesare Pautasso, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Olaf Schenk, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Alcherio Martinoli, EPFL, Switzerland (External Member)
• Prof. Alessandro Saffiotti, Örebro University, Sweden (External Member)