Synthesizing Priority Planning Formulae for Multi-Agent Pathfinding

Authors

  • Shuwei Wang University of Alberta
  • Vadim Bulitko University of Alberta
  • Taoan Huang University of Southern California
  • Sven Koenig University of Southern California
  • Roni Stern Ben Gurion University of the Negev

DOI:

https://doi.org/10.1609/aiide.v19i1.27532

Keywords:

Multi-agent Pathfinding, Prioritized Planning, Program Synthesis

Abstract

Prioritized planning is a popular approach to multi-agent pathfinding. It prioritizes the agents and then repeatedly invokes a single-agent pathfinding algorithm for each agent such that it avoids the paths of higher-priority agents. Performance of prioritized planning depends critically on cleverly ordering the agents. Such an ordering is provided by a priority function. Recent work successfully used machine learning to automatically produce such a priority function given good orderings as the training data. In this paper we explore a different technique for synthesizing priority functions, namely program synthesis in the space of arithmetic formulae. We synthesize priority functions expressed as arithmetic formulae over a set of meaningful problem features via a genetic search in the space induced by a context-free grammar. Furthermore we regularize the fitness function by formula length to synthesize short, human-readable formulae. Such readability is an advantage over previous numeric machine-learning methods and may help explain the importance of features and how to combine them into a good priority function for a given domain. Moreover, our experimental results show that our formula-based priority functions outperform existing machine-learning methods on the standard benchmarks in terms of success rate, run time and solution quality without using more training data.

Downloads

Published

2023-10-06

How to Cite

Wang, S., Bulitko, V., Huang, T., Koenig, S., & Stern, R. (2023). Synthesizing Priority Planning Formulae for Multi-Agent Pathfinding. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 19(1), 360-369. https://doi.org/10.1609/aiide.v19i1.27532