AI Planning in Our Research Group

Contents

• Projects
• Research Group
• Contact
• Funding
• AI planning resource material

Projects

• With Gaojian Fan and Rob Holte, Merge and Shrink abstractions in planning
• Random walks for best-first search and the Jasper planner, Fan Xie's thesis research 2011-2016.

  F. Xie. Exploration in Greedy Best-First Search for Satisficing Planning. PhD thesis, University of Alberta, 2016. Faculty of Science Dissertation Award

  R. Valenzano and F. Xie. On the Completeness of Best-First Search Variants that Use Random Exploration. AAAI-16, pages 784-790, 2016.

  F. Xie, M. Müller and R. Holte. Understanding and Improving Local Exploration for GBFS. ICAPS 2015, pages 244-248.

  F. Xie, M. Müller and R. Holte. Jasper: the Art of Exploration in Greedy Best First Search. In M. Vallati, L. Chrpa, L. and T. McCluskey, The Eighth International Planning Competition, University of Huddersfield, p. 39-42, 2014.
  Update Nov 28, 2014: the version linked above replaces the IPC booklet version. It fixes a typo in Table 1: the coverage of LAMA-2011 was 1913 out of a total of 2112, not 2113.

  F. Xie, M. Müller, R. Holte and T. Imai. Type-based Exploration for Satisficing Planning with Multiple Search Queues . AAAI 2014, p. 2395-2401, 2014.

  F. Xie, M. Müller, R. Holte and T. Imai. Type-based Exploration with Multiple Search Queues for Satisficing Planning. ICAPS-2014 Workshop on Heuristics and Search for Domain-independent Planning, 62-70. A slightly extended version of the AAAI paper above. 2014.

  F. Xie, M. Müller and R. Holte. Adding Local Exploration to Greedy Best-First Search for Satisficing Planning . AAAI 2014, p. 2388-2394, 2014.

  F. Xie, M. Müller and R. Holte. Adding Local Exploration to Greedy Best-First Search in Satisficing Planning. ICAPS-2014 Workshop on Heuristics and Search for Domain-independent Planning, 53-61. A slightly extended version of the AAAI paper above. 2014.

  F. Xie, R. Valenzano and M. Müller. Better time constrained search via randomization and postprocessing. ICAPS 2013, pages 269-277, 2013.

  F. Xie, R. Valenzano and M. Müller. Better time constrained search via randomization and postprocessing. Technical Report TR 13-02, Dept. of Computing Science. University of Alberta, Edmonton, Alberta, Canada, 2013.

  Arvand-LS adds local search to the Arvand framework. It improves both quality and coverage compared to Arvand and scales well to larger problem instances. F. Xie, H. Nakhost and M. Müller. Planning via Random Walk-Driven Local Search. In ICAPS, 2012.

  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.

• Planning with Monte Carlo Random Walks, Arvand, Aras etc. Hootan Nakhost's PhD research 2008-2013. Arvand is a competitive planner which introduced the approach of Monte Carlo Random Walks into classical planning. Our IJCAI 2009, SOCS 2012, IJCAI 2013 and AI Communications papers as well as Hootan's PhD thesis develop this method.

  H. Nakhost and M. Müller. Monte-Carlo exploration for deterministic planning. In Twenty-first International Joint Conference on Artificial Intelligence (IJCAI), pages 1766-1771, Pasadena, California, USA, 2009.

  We have developed theoretical models that explain when and why random walks work in planning.
  H. Nakhost and M. Müller. A Theoretical Framework for Studying Random Walk Planning. In SOCS, 2012.

  H. Nakhost and M. Müller. Towards a Theory of Random Walk Planning: Regress Factors, Fair Homogeneous Graphs, and Extensions. AI Communications 27, 329-344. 2014. (pre-print)

  H. Nakhost and M. Müller. Towards a second generation random walk planner: an experimental exploration. IJCAI 2013, pages 2336-2342. Errata for this paper.

  H. Nakhost. Random Walk Planning: Theory, Practice, and Application. PhD thesis, University of Alberta, 2013. Dissertation Award for best PhD thesis from the Canadian Artificial Intelligence Association.

  Arvand participated successfully in the satisficing track of the IPC 2011 planning competition.

  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.

• ArvandHerd is the leading parallel portfolio planner. It consists of several copies of Arvand plus one copy of LAMA. ArvandHerd won the parallel satisficing track of the IPC 2011 and 2014 planning competitions. It was also entered in the 2018 competition, but the parallel track was cancelled because of the low number (2) of participants.

  ArvandHerd code:

  • 2018 competition versions on BitBucket, adapted to run in a Singularity container: Regular and 32 core version (experimental)
  • 2014 competition version on github.

  R. Valenzano, H. Nakhost, M. Müller, J. Schaeffer and N. Sturtevant. ArvandHerd 2014. In M. Vallati, L. Chrpa, L. and T. McCluskey, The Eighth International Planning Competition, University of Huddersfield, p. 1-5, 2014.

  R. Valenzano, H. Nakhost, M. Müller, J. Schaeffer, and N. Sturtevant. ArvandHerd: Parallel Planning with a Portfolio. In ECAI, 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.

• In collaboration with Jorg Hoffmann of University of Saarland, we studied Random Walk-based methods in Resource-Constrained Planning, 2010-2012. 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.

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

  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.

• 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 and the extended technical report describe this method.

  H. Nakhost and M. Müller. Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement. 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.

  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.

• Motion planning with random walks. This was Weifeng Chen's MSc thesis research 2014-15. We applied the main ideas from Arvand to the domain of motion planning in robotics. We achieved similar results as state of the art motion planners, using only random walks from the start state and local information. We did not use any knowledge about the underlying space, which is required e.g. to generate random target destinations in RRT style planning.

  W. Chen. Motion Planning with Monte Carlo Random Walks. MSc thesis, University of Alberta, 2015.

  W. Chen and M. Müller. Continuous Arvand: Motion Planning with Monte Carlo Random Walks. 3rd ICAPS Workshop on Planning and Robotics (PlanRob 2015), pages 23-34. (pre-print)

• Macro-FF (Adi's page at NICTA), is an adaptive domain-independent planner built on top of FF 2.3. It learns macros from previous domain experience, from solving sample problems.

  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.

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

  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.

  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.

  A. Botea, M. Enzenberger, M. Müller, and J. Schaeffer. Macro-FF. In booklet of the International Planning Competition (IPC-4), 2004.

  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.

  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.

  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.

• Other planning-related publications:

  F. Xie, A. Botea and A. Kishimoto. A Scalable Approach to Chasing Multiple Moving Targets with Multiple Agents. IJCAI 2017.
  Fan's internship at IBM Research in Dublin, which led to this paper, also led to a US Patent Application (!) for "Pro-active fuel and battery refilling for vehicles".

  F. Xie, A. Botea and A. Kishimoto. Heuristic-Aided Compressed Distance Databases. AAAI-2015 Workshop on Planning, Search and Optimization, pages 85-91, 2015.

  R. Valenzano, N. Sturtevant, J. Schaeffer and F. Xie. A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration. ICAPS 2014, p. 375-379, 2014.

  A. Botea, M. Müller, and J. Schaeffer. Near optimal hierarchical path-finding. Journal of Game Development, 1(1):7-28, 2004.

Research Group, Collaborators and Alumni

• Gaojian Fan, PhD student
• Rob Holte, co-supervisor for Gaojian Fan, Merge and Shrink abstractions
• Martin Müller, Faculty

Collaborators

• Joerg Hoffmann, University of Saarland, Resource-Constrained Planning
• Rick Valenzano, Element AI, ArvandHerd
• Jonathan Schaeffer, University of Alberta, ArvandHerd
• Nathan Sturtevant, University of Alberta, ArvandHerd

UofA Planning Alumni

• Fan Xie, PhD 2016. Now at Google Waterloo.
• Weifeng Chen, MSc 2015. Now at Amazon Web Services.
• Hootan Nakhost, PhD 2013. Now at Google Waterloo.
• 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 IBM Research, Dublin.
• Finnegan Southey Postdoc, Topic: Planning in games. Now at Google research.

Contact

Please contact one of the current group members for more information.

Funding

Our research is funded by NSERC, the Natural Sciences and Engineering Research Council of Canada, and GRAND NCE, one of the Government of Canada's Networks of Centres of Excellence.