Choosing the Initial State for Online Replanning

Authors

  • Maximilian Fickert Saarland University
  • Ivan Gavran Max Planck Institute for Software Systems
  • Ivan Fedotov Max Planck Institute for Software Systems
  • Jörg Hoffmann Saarland University
  • Rupak Majumdar Max Planck Institute for Software Systems
  • Wheeler Ruml University of New Hampshire

DOI:

https://doi.org/10.1609/aaai.v35i14.17461

Keywords:

Heuristic Search, Deterministic Planning

Abstract

The need to replan arises in many applications. However, in the context of planning as heuristic search, it raises an annoying problem: if the previous plan is still executing, what should the new plan search take as its initial state? If it were possible to accurately predict how long replanning would take, it would be easy to find the appropriate state at which control will transfer from the previous plan to the new one. But as planning problems can vary enormously in their difficulty, this prediction can be difficult. Many current systems merely use a manually chosen constant duration. In this paper, we show how such ad hoc solutions can be avoided by integrating the choice of the appropriate initial state into the search process itself. The search is initialized with multiple candidate initial states and a time-aware evaluation function is used to prefer plans whose total goal achievement time is minimal. Experimental results show that this approach yields better behavior than either guessing a constant or trying to predict replanning time in advance. By making replanning more effective and easier to implement, this work aids in creating planning systems that can better handle the inevitable exigencies of real-world execution.

Downloads

Published

2021-05-18

How to Cite

Fickert, M., Gavran, I., Fedotov, I., Hoffmann, J., Majumdar, R., & Ruml, W. (2021). Choosing the Initial State for Online Replanning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12311-12319. https://doi.org/10.1609/aaai.v35i14.17461

Issue

Section

AAAI Technical Track on Search and Optimization