Jonas Kvarnström
Department of Computer and Information Science, Linköping University, Sweden
Download article
Published in: The Swedish AI Society Workshop May 20-21; 2010; Uppsala University
Linköping Electronic Conference Proceedings 48:9, p. 45-54
Published: 2010-05-19
ISBN:
ISSN: 1650-3686 (print), 1650-3740 (online)
Partially ordered plan structures are highly suitable for centralized multi-agent planning; where plans should be minimally constrained in terms of precedence between actions performed by different agents. In many cases; however; any given agent will perform its own actions in strict sequence. We take advantage of this fact to develop a hybrid of temporal partial order planning and forward-chaining planning. A sequence of actions is constructed for each agent and linked to other agents’ actions by a partially ordered precedence relation as required. When agents are not too tightly coupled; this structure enables the generation of partial but strong information about the state at the end of each agent’s action sequence. Such state information can be effectively exploited during search. A prototype planner within this framework has been implemented; using precondition control formulas to guide the search process.
[1] F. Bacchus and M. Ady. Precondition control. Available at http://www.cs.toronto. edu/fbacchus/Papers/BApre.pdf; 1999.
[2] F. Bacchus and F. Kabanza. Using temporal logics to express search control knowledge for planning. Artificial Intelligence; 116(1-2):123–191; 2000.
[3] C. B¨ackstr¨om. Computational aspects of reordering plans. Journal of Artificial Intelligence Research; 9 (99):137; 1998.
[4] B. Bonet and H. Ge ner. HSP: Heuristic search planner. AI Magazine; 21(2); 2000.
[5] C. Boutilier and R. I. Brafman. Partial-order planning with concurrent interacting actions. Journal of Artificial Intelligence Research; 14:105–136; 2001.
[6] R. I. Brafman and C. Domshlak. From one to many: Planning for loosely coupled multi-agent systems. In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS); pages 28–35; Sydney; Australia; 2008.
[7] M. Brenner. Multiagent planning with partially ordered temporal plans. In Proc. IJCAI; 2003.
[8] J. Ho mann and B. Nebel. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research; 14:253–302; 2001.
[9] J. Kvarnstr¨om and P. Doherty. TALplanner: A temporal logic based forward chaining planner. Annals of Mathematics and Artificial Intelligence; 30:119–169; June 2000.
[10] E. D. Sacerdoti. The nonlinear nature of plans. In Proceedings of the 4th International Joint Conference on Artificial Intelligence; pages 206–214. Morgan Kaufmann Publishers Inc.; 1975.
[11] M. Veloso and P. Stone. FLECS: Planning with a flexible commitment strategy. Journal of Artificial Intelligence Research; 3:25–52; 1995.
[12] D. S. Weld. An introduction to least commitment planning. AI magazine; 15(4):27; 1994.
