Towards Robust Multiagent Plans
Achieving joint objectives by teams of cooperative planning agents requires significant reasoning but also coordination and communication efforts especially in case of planning in dynamic environments. The robustness of the resulting plans with respect to unforeseen changes is a key property. The research fields tackling such problems are uncertainty planning, continuous and online planning, plan repairing and probabilistic planning. This project focuses on study of various approaches from these fields and the key objective is to extend the approaches to multiagent setting and therefore to area of distributed problem solving in general. The research targets comprise:
Formal modelling. Formalization of multiagent planning problems towards the robustness against the uncertainty and dynamism in the environment. Its mathematical models, specification of descriptive languages for representing the problems and formal study of computational complexity, interaction stability and other properties of robust multi-agent planning and multi-agent plans.
Algorithm design. Research review of existing planning and coordination algorithms matching the multiagent planning problem definition. Extension of existing planning methods (heuristic-based, sampling-based, plan adaptation-based) for robust multiagent planning. Suggest and develop various multiagent planning methods optimizing the selected planning criteria of the robust planning.
Theoretical analysis. Perform theoretical analysis of complexity metrics as computational complexity and communication complexity of the developed methods, study relationship between robust planning and multiagent planning techniques.
Empirical Analysis. Experimental analysis of the properties of the designed planning methods, validation of the theoretical results, analysis of their practical usability and generality. For this purpose we will develop a set of benchmark problems that will be used for analysis of the performance of the algorithms and deploy the algorithms into a high-fidelity simulation. The simulation system will be based on the Tactical AgentFly and Tactical AgentScout project (funded previously by US ARMY, CERDEC) as an experimental testbed. Tactical Environment is high-fidelity, large scale multiagent model of surveillance and tracking missions executed by a fleet of unmanned aerial vehicles.
Researchers involved: Antonín Komenda, Michal Pěchouček, Michal Štolba
Publications:
Carmel Domshlak. Fault Tolerant Planning: Complexity and Compilation. In Proceedings of International Conference on Automated Planning and Scheduling (ICAPS'13). 2013.
Vitaly Mirkis, Carmel Domshlak, Abstractions for Oversubscription Planning. In Proceedings of International Conference on Automated Planning and Scheduling (ICAPS'13). 2013.
Michal Štolba, Antonín Komenda: Fast-Forward Heuristic for Multiagent Planning. In Proceedings of the 1st Workshop on Distributed and Multi-Agent Planning (DMAP--ICAPS'13). 2013.
Antonín Komenda, Peter Novák, Michal Pěchouček: How to Repair Multiagent Plans: Experimental Approach. In Proceedings of the 1st Workshop on Distributed and Multi-Agent Planning (DMAP--ICAPS'13). 2013.
Michal Štolba, Antonín Komenda: Relaxation Heuristics for Multiagent Planning. In Proceedings of International Conference on Automated Planning and Scheduling (ICAPS'14). 2014.
Zohar Feldman, Carmel Domshlak, On MABs and Separation of Concerns in Monte-Carlo Planning for MDPs. In Proceedings of International Conference on Automated Planning and Scheduling (ICAPS'14). 2014.
Zohar Feldman, Carmel Domshlak, Monte-Carlo Tree Search: To MC or to DP?, In Proceedings of ECAI 2014 - 21st European Conference on Artificial Intelligence. 2014.
Vitaly Mirkis, Carmel Domshlak, Landmarks in Oversubscription Planning, In Proceedings of ECAI 2014 - 21st European Conference on Artificial Intelligence. 2014.
Alexander Shleyfman, Antonín Komenda, Carmel Domshlak: On Combinatorial Actions and CMABs with Linear Side Information. In Proceedings of 21st European Conference on Artificial Intelligence (ECAI'14). 2014.
Antonín Komenda, Alexander Shleyfman, and Carmel Domshlak: On Robustness of CMAB Algorithms: Experimental Approach. In Proceedings of ECAI Computer Games Workshop (CGW--ECAI'14). 2014.
Antonín Komenda, Peter Novák, Michal Pěchouček, Domain-independent multi-agent plan repair, Journal of Network and Computer Applications, Volume 37, January 2014, Pages 76-88.