×

zbMATH — the first resource for mathematics

The MADLA planner: multi-agent planning by combination of distributed and local heuristic search. (English) Zbl 1419.68100
Summary: Real world applications often require cooperation of multiple independent entities. Classical planning is a well established technique solving various challenging problems such as logistic planning, factory process planning, military mission planning and high-level planning for robots. Multi-agent planning aims at solving similar problems in the presence of multiple independent entities (agents). Even though such entities might want to cooperate in order to fulfill a common goal, they may want to keep their internal information and processes private. In such case, we talk about privacy-preserving multi-agent planning.
So far, multi-agent planners based on heuristic search used either a local heuristic estimating the particular agent’s local subproblem or a distributed heuristic estimating the global problem as a whole. In this paper, we present the Multi-Agent Distributed and Local Asynchronous (MADLA) Planner, running a novel variant of a distributed state-space forward-chaining multi-heuristic search which combines the use of a local and a distributed heuristic in order to combine their benefits. In particular, the planner uses two variants of the well known Fast-Forward heuristic. We provide proofs of soundness and completeness of the search algorithm and show how much and what type of privacy it preserves. We also provide an improved privacy-preserving distribution scheme for the Fast-Forward heuristic.
We experimentally compare the newly proposed multi-heuristic scheme and the two used heuristics separately. The results show that the proposed solution outperforms classical (single-heuristic) distributed search with either one of the heuristics used separately. In the detailed experimental analysis, we show limits of the planner and of the used heuristics based on particular properties of the benchmark domains. In a comprehensive set of multi-agent planning domains and problems, we show that the MADLA Planner outperforms all contemporary state-of-the-art privacy-preserving multi-agent planners using a compatible planning model.
MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T42 Agent technology and artificial intelligence
Software:
LPG; PDDL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Fikes, R.; Nilsson, N., STRIPS: a new approach to the application of theorem proving to problem solving, (Proceedings of the 2nd International Joint Conference on Artificial Intelligence (IJCAI’71), (1971)), 608-620
[2] Brafman, R. I.; Domshlak, C., From one to many: planning for loosely coupled multi-agent systems, (Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS’08), (2008)), 28-35
[3] Nissim, R.; Brafman, R., Distributed heuristic forward search for multi-agent planning, J. Artif. Intell. Res., 51, 293-332, (2014) · Zbl 1367.68325
[4] Nau, D.; Ghallab, M.; Traverso, P., Automated planning: theory & practice, (2004), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA · Zbl 1074.68613
[5] Nissim, R.; Brafman, R. I., Multi-agent A* for parallel and distributed systems, (Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’12), (2012)), 1265-1266
[6] Štolba, M.; Komenda, A., Relaxation heuristics for multiagent planning, (Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS’14), (2014)), 298-306
[7] Hoffmann, J.; Nebel, B., The FF planning system: fast plan generation through heuristic search, J. Artif. Intell. Res., 14, 253-302, (2001) · Zbl 0970.68044
[8] Štolba, M.; Komenda, A., Fast-forward heuristic for multiagent planning, (Proceedings of the 1st ICAPS Workshop on Distributed and Multi-Agent Planning (DMAP’13), (2013)), 75-83
[9] Pellier, D., Distributed planning through graph merging, (Proceedings of the 2nd International Conference on Agents and Artificial Intelligence (ICAART 2010), (2010)), 128-134
[10] Helmert, M., The fast downward planning system, J. Artif. Intell. Res., 26, 191-246, (2006) · Zbl 1182.68245
[11] Röger, G.; Helmert, M., The more, the merrier: combining heuristic estimators for satisficing planning, (Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS’10), (2010)), 246-249
[12] Mcdermott, D.; Ghallab, M.; Howe, A.; Knoblock, C.; Ram, A.; Veloso, M.; Weld, D.; Wilkins, D., PDDL - the planning domain definition language, (1998), Yale Center for Computational Vision and Control, Tech. Rep. TR-98-003
[13] Kovacs, D. L., A multi-agent extension of PDDL3.1, (Proceedings of the 3rd Workshop on the International Planning Competition (IPC), (2012)), 19-27
[14] Conry, S.; Kuwabara, K.; Lesser, V.; Meyer, R. A., Multistage negotiation for distributed constraint satisfaction, IEEE Trans. Syst. Man Cybern., 21, 6, 1462-1477, (1991) · Zbl 0825.68627
[15] Yokoo, M.; Suzuki, K.; Hirayama, K., Secure distributed constraint satisfaction: reaching agreement without revealing private information, (Van Hentenryck, P., Principles and Practice of Constraint Programming - CP 2002, Lecture Notes in Computer Science, vol. 2470, (2002), Springer Berlin/Heidelberg), 387-401
[16] Yao, A., How to generate and exchange secrets, (27th Annual Symposium on Foundations of Computer Science, 1986, (1986), IEEE), 162-167
[17] Gupta, D.; Segal, A.; Panda, A.; Segev, G.; Schapira, M.; Feigenbaum, J.; Rexford, J.; Shenker, S., A new approach to interdomain routing based on secure multi-party computation, (Proceedings of the 11th ACM Workshop on Hot Topics in Networks, (2012), ACM), 37-42
[18] Maliah, S.; Shani, G.; Stern, R., Privacy preserving landmark detection, (Proceedings of the 21st European Conference on Artificial Intelligence (ECAI’14), (2014)), 597-602
[19] Borrajo, D., Plan sharing for multi-agent planning, (Proceedings of the 1st ICAPS Workshop on Distributed and Multi-Agent Planning (DMAP’13), (2013)), 57-65
[20] Richter, S.; Westphal, M., The LAMA planner: guiding cost-based anytime planning with landmarks, J. Artif. Intell. Res., 39, 1, 127-177, (2010) · Zbl 1205.68383
[21] Chandy, K. M.; Lamport, L., Distributed snapshots: determining global states of distributed systems, ACM Trans. Comput. Syst., 3, 1, 63-75, (1985)
[22] Bylander, T., The computational complexity of propositional STRIPS planning, Artif. Intell., 69, 1-2, 165-204, (1994) · Zbl 0821.68065
[23] Torreño, A.; Onaindia, E.; Sapena, O., FMAP: distributed cooperative multi-agent planning, Appl. Intell., 41, 2, 606-626, (2014)
[24] Keyder, E.; Geffner, H., Heuristics for planning with action costs revisited, (Proceedings of the 18th European Conference on Artificial Intelligence (ECAI’08), (2008)), 588-592
[25] Crosby, M.; Rovatsos, M.; Petrick, R., Automated agent decomposition for classical planning, (Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS’13), (2013)), 46-54
[26] Tozicka, J.; Jakubuv, J.; Komenda, A., Generating multi-agent plans by distributed intersection of finite state machines, (Proceedings of the 21st European Conference on Artificial Intelligence (ECAI’14), (2014)), 1111-1112
[27] Nissim, R.; Brafman, R. I.; Domshlak, C., A general, fully distributed multi-agent planning algorithm, (Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’10), (2010)), 1323-1330
[28] Coles, A.; Fox, M.; Long, D.; Smith, A., Teaching forward-chaining planning with javaff, (Colloquium on AI Education, Twenty-Third AAAI Conference on Artificial Intelligence, (2008))
[29] Durkota, K.; Komenda, A., Deterministic multiagent planning techniques: experimental comparison (short paper), (Proceedings of the 1st ICAPS Workshop on Distributed and Multi-Agent Planning (DMAP’13), (2013)), 43-47
[30] Dimopoulos, Y.; Hashmi, M. A.; Moraitis, P., Extending SATPLAN to multiple agents, (Proceedings of the 30th International Conference on Innovative Techniques and Applications of Artificial Intelligence (SGAI’10), (2010)), 137-150 · Zbl 1208.68223
[31] Jonsson, A.; Rovatsos, M., Scaling up multiagent planning: a best-response approach, (Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS’11), (2011)), 114-121
[32] Fabre, E.; Jezequel, L.; Haslum, P.; Thiébaux, S., Cost-optimal factored planning: promises and pitfalls, (Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS’10), (2010)), 65-72
[33] Gerevini, A.; Serina, I., LPG: a planner based on local search for planning graphs with action costs, (Proceedings of the 6th International Conference on Artificial Intelligence Planning Systems (AIPS’02), (2002)), 13-22
[34] Luis, N.; Borrajo, D., Plan merging by reuse for multi-agent planning, (Proceedings of the 2nd ICAPS Workshop on Distributed and Multi-Agent Planning (DMAP’14), (2014)), 38-44
[35] Fox, M.; Gerevini, A.; Long, D.; Serina, I., Plan stability: replanning versus plan repair, (Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS’06), (2006)), 212-221
[36] Helmert, M.; Domshlak, C., Landmarks, critical paths and abstractions: What’s the difference anyway?, (Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS’09), (2009)), 162-169
[37] Helmert, M.; Haslum, P.; Hoffmann, J., Flexible abstraction heuristics for optimal sequential planning, (Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS’07), (2007)), 176-183
[38] Jezequel, L.; Fabre, E., A#: a distributed version of A* for factored planning, (Proceedings of the 51st IEEE Conference on Decision and Control (CDC’12), (2012)), 7377-7382
[39] Kvarnström, J., Planning for loosely coupled agents using partial order forward-chaining, (Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS’11), (2011)), 138-145
[40] Torreño, A.; Onaindia, E.; Sapena, O., An approach to multi-agent planning with incomplete information, (Proceedings of the 20th European Conference on Artificial Intelligence (ECAI’12), (2012)), 762-767
[41] Torreño, A.; Onaindia, E.; Sapena, O., FMAP: a heuristic approach to cooperative multi-agent planning, (Proceedings of the 1st ICAPS Workshop on Distributed and Multi-Agent Planning (DMAP’13), (2013)), 84-92
[42] Benton, J.; Coles, A. J.; Coles, A., Temporal planning with preferences and time-dependent continuous costs, (McCluskey, L.; Williams, B.; Silva, J. R.; Bonet, B., Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, ICAPS 2012, Atibaia, São Paulo, Brazil, June 25-19, 2012, (2012), AAAI)
[43] International planning competition, (2014)
[44] Komenda, A.; Stolba, M.; Kovacs, D. L., The international competition of distributed and multiagent planners (codmap), AI Mag., 37, 3, 109-115, (2016)
[45] Fišer, D.; Štolba, M.; Komenda MAPlan, A., (Proceedings of the Competition of Distributed and Multi-Agent Planners (CoDMAP-15), (2015)), 8-10
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.