The field of automated planning reaches the very beginnings of Artificial Intelligence (AI) research and it is tightly adherent to general problem solving. Such maturity in Computer Sciences research usually means that there is a large variety of stemming problem. One of such sub-fields is Multi-agent planning. In environments, where agents have their own goals, but they want to cooperate as well, it is necessary to look for common recipes, i.e., multi-agent plans. Using such plans, the agents fulfill the goals in a coordinated manner. Research field of multi-agent planning search for both theoretical guarantees and practical algorithms for solving of these problems. In ATG, we study several specific forms of multi-agent planning.

Deterministic domain-independent multi-agent planning

When people act together with either a shared purpose, or willing and being able to assist each other, they collaborate. Collaboration enables people to work more efficiently and to complete activities they could not accomplish individually. Reflecting this paradigm, an increasing number of computer applications developed to assist human decision makers collaborate between various systems and people. Situated within the field of multi-agent systems, the area of multi-agent planning and execution is devoted to exactly this paradigm of collaborative problem solving. Planning agents in this setting plan for individual or joint goals while coordinating their plans and planning processes, for example by negotiating tasks or resources.

According to our research review of prior art, there is extreme lack of public out-of-the-box domain-independent multi-agent planners. The first steps towards such a planning system have been made only recently. We plan to make deeper study of this problem and come up with a domain-independent multi-agent planning system straightforwardly usable as current single-agent planners.

Related projects:

  • past: -
  • ongoing: Deterministic Domain-independent Multi-agent Planning
  • planned: Heuristic Search for Multiagent and Factored Planning

Robust multi-agent planning

Achieving joint objectives by teams of cooperative planning agents requires significant reasoning but also coordination and communication efforts. Several formal models and planning algorithms for multi-agent planning have been proposed and studied in last years. These models combine the concepts  from the fields of automated planning and multi-agent systems (e.g. distributed constraint satisfaction). The challenge of the proposed research effort is to extend the existing work in multi-agent planning towards robustness of the resulting plans with respect to unforeseen changes in the environment. Robustness of multi-agent planning can be achieved either by sophisticated plan repair methods or by capability to produce plans that are independent of certain class of changes of the environment.

For a single-agent system facing a plan failure in a dynamic environment, attempts to repair the failed plan provide often little benefits over initiation of a new planning process, reflecting the change in the environment. However, in multi-agent settings the right choice of plan repair methods may have an important impact on the overall communication complexity and coordination costs of the planning and plan execution processes. A high communication overhead might be even prohibitive in certain domains. We hypothesize that in decentralized systems, where coordination is enforced to achieve joint objectives, attempts to repair failed multi-agent plans should lead to lower communication overhead and coordination costs than re-planning from scratch.

Related projects:

  • past: I-Globe; Tactical AgentScout 1, 2
  • ongoing: Towards Robust Multiagent Plans 1+2
  • planned: -

Multi-agent optimization & planning with limited resources

Intelligent agents acting in environments based on real-world assumptions usually have to consider various optimization problems on resources during planning. These problems of mathematical optimization include usually hard problems as Distributed Vehicle Routing Problem, Trading  Salesman Problem.

The problem of distributed decision making, decentralized planning and controlling entities in heterogeneous distributed environments is crucial for many application domains. Existing centralized methods depend on one central planning system that gathers all required data about decentralized entities before the planning process starts. This approach faces various difficulties. One problem is the need for sharing private knowledge and information about the actual status of these entities. The other problem is the need for real-time re-planning based on environments and conditions changing dynamically in time. In the multi-agent approaches, each entity is in charge of suggesting their individual plans where cooperation, resource sharing and conflict resolution is solved by methods of negotiation. Distributed planning can be viewed as either (i) planning for activities and resources allocated among distributed agents, (ii) distributed (parallel) computation aimed at plan construction or (iii) plan merging activity. In this sub-field we are solving the problem by algorithms based on task allocation and local resource planning in cooperative environments and use the delegation for continual solution improvement, that is performed in non-critical time.

Related projects:

  • past: I-Globe; Tactical AgentFly 1, 2
  • ongoing: -
  • planned: -

Multi-agent trajectory and path planning

When mobile agents operate in a shared space, one of the essential tasks for them is to prevent mutual collisions. Prominent examples of domains requiring robust collision avoidance techniques are different kinds of autonomous multi-robotic systems, next-generation air traffic management systems, road traffic management systems etc.

A range of methods is being currently employed to realize a safe and efficient operation of a number of agents within a shared space. Some of the methods assume a cooperative setting where all the involved agents work together to solve their mutual conflicts, others assume a non-cooperative setting where the agents cannot coordinate their actions, and yet others consider pursuit-evasion adversarial scenarios where a solution is a trajectory that is collision-free against the worst-case behaviour of other agents. 

In our work, we developed several decentralized methods that allow a number of agents to cooperatively find corresponding conflict-free trajectories optimizing some given quality criterion. In result, these methods can be used to ensure that the available common space or transport infrastructures is utilized in a safe and efficient way.

Related projects:

  • past: AgentFly; I-Globe; Tactical AgentScout 1, 2; Tactical AgentFly 1, 2, 3; AgentPolis; AgentCrowd;
  • ongoing: SuperHub, AgentDrive
  • planned: -

People

Antonín Komenda (contact person), Jiří Vokřínek (contact person), Michal Čáp, Adam Horký, Jan Hrnčíř, Ondřej Hrstka, Viliam Lisý, Tomáš Meiser, Martin Selecký, Jan Stiborek, Michal Štolba, Jan Tožička

Publications

Antonín Komenda and Peter Novák and Michal Pěchouček: Decentralized Multi-agent Plan Repair in Dynamic Environments (Extended Abstract). In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012). 2012, vol. 3, p. 1239-1240.

Michal Cap and Peter Novak and Jiri Vokrinek and Michal Pechoucek: Asynchronous Decentralized Algorithm for Space-Time Cooperative Pathfinding. In International Workshop on Spatio-Temporal Dynamics at ECAI 2012 (to appear). 2012. 

Antonin Komenda and Jiri Vokrinek and Michal Pechoucek: Plan representation and execution in multi-actor scenarios by means of social commitments. Web Intelligence and Agent Systems. 2011, vol. 9, p. 123-133. ISSN 1570-1263. 

Lukas Chrpa and Antonin Komenda: Smoothed Hex-grid Trajectory Planning Using Helicopter Dynamics. In Proceedings of International Conference on Agents and Artificial Intelligence (ICAART). SciTePress, 2011, vol. 1, p. 629--632. ISBN 978-989-8425-40.

Vokrinek, J. and Komenda , A. and Pechoucek , M.: Abstract Architecture for Task-oriented Multi-agent Problem Solving. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on. 2011, vol. 41, p. 31 -40. ISSN 1094-6977. 

Jiri Vokrinek and Antonin Komenda and Michal Pechoucek: Cooperative Agent Navigation in Partially Unknown Urban Environments. In PCAR '10: The Third International Symposium on Practical Cognitive Agents and Robots. Proceedings of the AAMAS-10 Workshops.. Toronto, Canada: IFAAMAS: Internatioal Foundation for Autonomous Agents and Multiagent Systems, 2010, p. 46-53. ISBN 0-98265-710-0.

Jiri Vokrinek and Antonin Komenda and Michal Pechoucek: Agents Towards Vehicle Routing Problems. In AAMAS 2010: Proceedings of the Ninth International Conference on Autonomous Agents and Multi-Agent Systems. Toronto, Canada: IFAAMAS: Internatioal Foundation for Autonomous Agents and Multiagent Systems, 2010, p. 773-780. ISBN 0-98265-710-0/978-0-9826571-1-9.

Antonin Komenda and Jiri Vokrinek and Dusan Pavlicek and Michal Pechoucek and Gerhard Wickler and Jeff Dalton and Austin Tate: Distributed Planning and Coordination in Non-deterministic Environments (Demo). In Proceedings of The Eight International Conference on Autonomous Agents and Multiagent Systems. 2009.

Jiri Vokrinek and Antonin Komenda and Michal Pechoucek: Decommitting in Multi-agent Execution in Non-deterministic Environment: Experimental Approach. In Proceedings of The Eight International Conference on Autonomous Agents and Multiagent Systems. 2009. 

Gerhard Wickler and Michal Pechoucek and Antonin Komenda and Jiri Vokrinek and Austin Tate: Multi-Agent Planning with Decommitment. In Proceesings of Knowledge Systems for Coalition Operations (KSCO 2009). 2009. 

Antonin Komenda and Jiri Vokrinek and Michal Pechoucek and Gerhard Wickler and Jeff Dalton and Austin Tate: I-Globe: Distributed Planning and Coordination of Mixed-initiative Activities. In Proceedings of Knowledge Systems for Coalition Operations (KSCO 2009). 2009.

Antonin Komenda and Michal Pechoucek and Jiri Biba and Jiri Vokrinek: Planning and Re-planning in Multi-actors Scenarios by means of Social Commitments. In Proceedings of the International Multiconference on Computer Science and Information Technology (IMCSIT/ABC 2008). IEEE, 2008, vol. 3, p. 39-45. ISBN 978-83-60810-1. 

Jiri Hodik and Petr Becvar and Michal Pechoucek and Jiri Vokrinek and Jiri Pospisil: ExPlanTech and ExtraPlanT: multi-agent technology for production planning, simulation and extra-enterprise collaboration. International Journal of Computer Systems Science and Engineering. 2005, vol. 20, p. 357-367. ISSN 0267-6192.

Michal Pechoucek and Ales Riha and Jiri Vokrinek and Vladimir Marik and Vojtech Prazma: ExPlanTech: Applying Multi-agent Systems in Production Planning. International Journal of Production Research. 2002, vol. 40, p. 3681-3692. ISSN 0020-7543.