Planning in Artificial Intelligence

Contents

• Projects
• Research Group
• Publications

Projects

• Arvand, a competitive planner based on the new approach of Monte Carlo Random Walks. Our IJCAI-09 paper describes this method. See link below under publications. Arvand participated successfully in the satisficing track of the IPC 2011 planning competition.
• Arvand-LS adds local search to the Arvand framework. See our ICAPS 2012 paper.
• ArvandHerd is a parallel portfolio planner consisting of several copies of Arvand plus one copy of LAMA. ArvandHerd won the parallel satisficing track of the IPC 2011 planning competition.
• In collaboration with Jorg Hoffmann of INRIA, we study Random Walk-based methods in Resorce-Constrained Planning. Two new techniques implemented in Arvand, On-Path Search Continuation (OPSC) and Smart Restarts (SR), work well in these domains. See our SOCS-10 abstract and ICAPS 2012 paper.
• Aras, is a postprocessor for improving the quality of a given plan. It is a necessary complement to Arvand, which can produce low-quality plans containing many convoluted paths. However, is also effective for other satisficing planners. Our ICAPS 2010 paper, Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement, describes this method. See link below under publications.
• Macro-FF, (UofA page), (Adi's new page), is an adaptive domain-independent planner built on top of FF 2.3. It learns macros from previous domain experience, from solving sample problems. See our JAIR paper on Macro-FF listed below.

Research Group and Alumni

• Hootan Nakhost, PhD student
• Fan Xie, MSc student
• Martin Müller Faculty

UofA Planning Alumni

• Markus Enzenberger Senior programmer/analyst 2002-2009, Topics: uaplan system, macro-FF. Now software developer in Munich, Germany.
• Adi Botea PhD 2005, Topic: Improving Planning and Search with Automatic Abstraction. Now at NICTA and ANU, Canberra, Australia.
• Finnegan Southey Postdoc, Topic: Planning in games. Now at Google research.

Publications

H. Nakhost, J. Hoffmann and M. Müller. Resource-Constrained Planning: A Monte Carlo Random Walk Approach. Accepted for ICAPS, 2012.

F. Xie, H. Nakhost and M. Müller. Planning via Random Walk-Driven Local Search. Accepted for ICAPS, 2012.

R. Valenzano, H. Nakhost, M. Müller, J. Schaeffer, and N. Sturtevant. ArvandHerd: Parallel Planning with a Portfolio. 2011 International Planning Competition (IPC 2011) Planner Description Booklet.

H. Nakhost, M. Müller, R. Valenzano, and F. Xie. Arvand: the Art of Random Walks. 2011 International Planning Competition (IPC 2011) Planner Description Booklet.

F. Xie, H. Nakhost and M. Müller. A Local Monte Carlo Tree Search Approach in Deterministic Planning. AAAI Conference on Artificial Intelligence Student Abstract and Poster Program (SA-11), pages 1832-1833, 2011.

H. Nakhost, J. Hoffmann and M. Müller. Improving Local Search for Resource-Constrained Planning. Extended abstract. Proceedings of the Third Annual Symposium on Combinatorial Search (SOCS-10), pages 81-82, Stone Mountain, Atlanta, GA, USA, 2010.

• download from aaai.org

H. Nakhost and M. Müller. Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement, 2010. International Conference on Automated Planning and Scheduling (ICAPS-2010), pages 121-128, 2010. Editors R. Brafman, H. Geffner, J. Hoffmann and H. Kautz. AAAI Press, Toronto, Canada. Acceptance rate: 37/108 = 34%.

• download from aaai.org

H. Nakhost and M. Müller. Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement - Extended Version, 2010. Technical report TR 10-01, Dept. of Computing Science. University of Alberta.

• download page

H. Nakhost and M. Müller. Monte-Carlo exploration for deterministic planning, 2009. In Twenty-first International Joint Conference on Artificial Intelligence (IJCAI), pages 1766-1771, Pasadena, California, USA, 2009. Acceptance rate: 331/1290 = 26%.

• pdf

A. Botea, M. Müller, and J. Schaeffer. Fast planning with iterative macros. In Twentieth International Joint Conference on Artificial Intelligence (IJCAI), pages 1828-1833, Hyderabad, India, 2007. Acceptance rate (oral presentation): 212/1353 = 15.7%.

• pdf, 168k.

A. Botea. Improving AI Planning and Search with Automatic Abstraction. PhD thesis, University of Alberta, 2006.

• pdf.

A. Botea, M. Enzenberger, M. Müller, and J. Schaeffer. Macro-FF: Improving AI planning with automatically learned macro-operators. Journal of Artificial Intelligence Research, 24:581-621, 2005.

• JAIR page.

A. Botea, M. Müller, and J. Schaeffer. Learning partial-order macros from solutions. In S. Biundo, K. Myers, and K. Rajan, editors, ICAPS 2005. Proceedings of the 15th International Conference on Automated Planning and Scheduling, pages 231-240, Monterey, California, 2005.

• pdf, 484k.

A. Botea, M. Enzenberger, M. Müller, and J. Schaeffer. Macro-FF, 2004. In booklet of the International Planning Competition (IPC-4). http://ls5-www.cs.uni-dortmund.de/~edelkamp/ipc-4/IPC-4.pdf.

A. Botea, M. Müller, and J. Schaeffer. Using component abstraction for automatic generation of macro-actions. In S. Zilberstein, J. Koehler, and S. Koenig, editors, ICAPS 2004. Proceedings of the 14th International Conference on Automated Planning and Scheduling, pages 181-190, Whistler, Canada, 2004.

• pdf, 183k.

A. Botea, M. Müller, and J. Schaeffer. Using abstraction for planning in Sokoban. In J. Schaeffer, M. Müller, and Y. Björnsson, editors, Computers and Games 2002, number 2883 in Lecture Notes in Computer Science, pages 360-375. Springer Verlag, 2003.

• pdf, 546k.

A. Botea, M. Müller, and J. Schaeffer. Extending PDDL for hierarchical planning and topological abstraction. In iCAPS workshop on PDDL, pages 25-32, 2003.

A. Botea. Reducing planning complexity with topological abstraction. Proceedings of the International Conference on Automated Planning & Scheduling (ICAPS-03) Doctoral Consortium, Trento, Italy, 2003.

A. Botea. Using abstraction for heuristic search and planning. In S. Koenig and R. Holte, editors, 5th International Symposium on Abstraction, Reformulation, and Approximation, number 2371 in Lecture Notes in Computer Science, pages 326-327. Springer Verlag, 2002. Created: Dec 19, 2003 Last modified: Feb 15, 2012