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.
Multi-agent planning has long crossed the border of basic research, and there are numerous success stories of deploying effective multi-agent planning systems in space missions, manufacturing systems, supply-chain management, etc. However, so far the research on multi-agent planning has mostly focused on developing algorithms for specific problem domains. In turn, the industrial applications of multi-agent planning also rely on project-specific, procedurally encoded solutions. This approach has several crucial drawbacks. First, problem-specific solutions are typically hard to generalize, and thus it is hard (if at all possible) to apprehend the impact of each concrete research artefact on the area as a whole. As a result, inter-project reuse of algorithmic techniques developed in the area remains very challenging. Second, if a system requires a non-trivial multi-agent planning solution, then developing, implementing, and testing such a solution is likely to be cumbersome, time-consuming, and possibly even cost-inefficient. This overhead unavoidably slows down adoption of new technologies by the industry. Finally, as collaboration-oriented systems ultimately aim at connecting heterogeneous, independently developed systems, the lack of standardization in specifying multi-agent planning problems becomes a substantial obstacle on the way to scaling up the coverage of the systems.
While in available artificial intelligence literature multi-agent planning often relates to decentralized partial observable Markov decision process (Dec-POMDPs), or to a collection of methods for domain-specific planning for a community of autonomous agents (TALPlanner, GPGP), in the proposed project we aim solving the problem of deterministic distributed planning. Our objective is to design a planner to solve problems of Deterministic Domain-independent Multi-agent Planning (DDIMAP) as an abstract multi-agent reasoner which can be applied in a series of decentralized, multi-actor coordination scenarios (such as collective robotics, traffic and public transport or web-service orchestration). During the project we will (i) provide formalization of the domain DDIMAP planning problem, (ii) propose and design specific DDIMAP algorithm, (iii) carry out its theoretical complexity analysis and empirical evaluation.
Involved: Michal Pěchouček, Antonín Komenda, Jan Tožička, Jan Jakubův
Publications:
Karel Durkota, Antonín Komenda: Deterministic Multiagent Planning Techniques: Experimental Comparison (Short paper). In Proceedings of the 1st Workshop on Distributed and Multi-Agent Planning (DMAP--ICAPS'13). 2013.
Jan Tozicka, Jan Jakubuv, Antonin Komenda: Multiagent Planning by Iterative Negotiation over
Distributed Planning Graphs. In Proceedings of the 2nd Workshop on Distributed and Multi-Agent Planning (DMAP--ICAPS'14). 2013.
Michal Štolba, Antonín Komenda: Relaxation Heuristics for Multiagent Planning. In Proceedings of International Conference on Automated Planning and Scheduling (ICAPS'14). 2014.
Jan Tozicka, Jan Jakubuv, Karel Durkota, Antonin Komenda, Multiagent Planning Supported by Plan Diversity Metrics and Landmark Actions. In Proceedings of ICAART 2014 : International Conference on Agents and Artificial Intelligence. 2014.
Jan Tozicka, Jan Jakubuv, Antonin Komenda, Generating Multi-Agent Plans by Distributed Intersection of Finite State Machines. In Proceedings of ECAI 2014 - 21st European Conference on Artificial Intelligence. 2014.
Jan Tozicka, Jan Jakubuv, Antonin Komenda: Multiagent Planning by Plan Set Intersection and Plan Verification. In Proceedings of ICAART 2015 : International Conference on Agents and Artificial Intelligence. 2015.
Antonin Komenda, P. Novák, Michal Pěchouček : Multiagent Plan Repair by Combined Prefix and Suffix Reuse, Multiagent and Grid Systems (ISSN 1574-1702, vol. 11, Issue 1), 33-57. 2015.