A Formal Metareasoning Model of Concurrent Planning and Execution


  • Amihay Elboher Ben-Gurion University of the Negev
  • Ava Bensoussan Ben Gurion University of the Negev
  • Erez Karpas Technion
  • Wheeler Ruml University of New Hampshire
  • Shahaf S. Shperberg Ben-Gurion University of the Negev
  • Eyal Shimony Ben-Gurion University of the Negev




SO: Metareasoning and Metaheuristics, SO: Heuristic Search


Agents that plan and act in the real world must deal with the fact that time passes as they are planning. When timing is tight, there may be insufficient time to complete the search for a plan before it is time to act. By commencing execution before search concludes, one gains time to search by making planning and execution concurrent. However, this incurs the risk of making incorrect action choices, especially if actions are irreversible. This tradeoff between opportunity and risk is the problem addressed in this paper. Our main contribution is to formally define this setting as an abstract metareasoning problem. We find that the abstract problem is intractable. However, we identify special cases that are solvable in polynomial time, develop greedy solution algorithms, and, through tests on instances derived from search problems, find several methods that achieve promising practical performance. This work lays the foundation for a principled time-aware executive that concurrently plans and executes.




How to Cite

Elboher, A., Bensoussan, A., Karpas, E., Ruml, W., Shperberg, S. S., & Shimony, E. (2023). A Formal Metareasoning Model of Concurrent Planning and Execution. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), 12427-12435. https://doi.org/10.1609/aaai.v37i10.26464



AAAI Technical Track on Search and Optimization