Abstract
Devising intelligent robots or agents that interact with humans is a major challenge for artificial intelligence. In such contexts, agents must constantly adapt their decisions according to human activities and modify their goals. In this paper, we tackle this problem by introducing a novel planning approach, called Moving Goal Planning (MGP), to adapt plans to goal evolutions. This planning algorithm draws inspiration from Moving Target Search (MTS) algorithms. In order to limit the number of search iterations and to improve its efficiency, MGP delays as much as possible triggering new searches when the goal changes over time. To this purpose, MGP uses two strategies: Open Check (OC) that checks if the new goal is still in the current search tree and Plan Follow (PF) that estimates whether executing actions of the current plan brings MGP closer to the new goal. Moreover, MGP uses a parsimonious strategy to update incrementally the search tree at each new search that reduces the number of calls to the heuristic function and speeds up the search. Finally, we show evaluation results that demonstrate the effectiveness of our approach.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Pellier, D., Fiorino, H., Métivier, M.: A new approach for continual planning. In: AAMAS, pp. 1115–1116 (2013)
Nebel, B., Koehler, J.: Plan reuse versus plan generation: A theoretical and empirical analysis. Artificial Intelligence 76, 427–454 (1995)
van der Krogt, R., de Weerdt, M.: Plan repair as an extension of planning. In: ICAPS, pp. 161–170 (2005)
Fox, M., Gerevini, A., Long, D., Serina, I.: Plan stability: Replanning versus plan repair. In: ICAPS, pp. 212–221 (2006)
Ishida, T., Korf, R.: Moving target search. In: IJCAI, pp. 204–210 (1991)
Korf, R.: Real-Time Heuristic Search. Artificial Intelligence 42(2-3), 189–211 (1990)
Melax, S.: New approaches to moving target search. In: AAAI Falls Symp. Game Planning Learn., pp. 30–38 (1993)
Koenig, S., Likhachev, M.: Adaptive A*. In: AAMAS, pp. 1311–1312 (2005)
Koenig, S., Likhachev, M., Sun, X.: Speeding up moving target search. In: AAMAS (2007)
Sun, X., Koenig, S., Yeoh, W.: Generalized adaptive A*. In: AAMAS, pp. 469–476 (2008)
Stenz, A.: The focused D* algorithm for real-time replanning. In: IJCAI, pp. 1642–1659 (1995)
Sun, X., Yeoh, W., Koenig, S.: Efficient incremental search for moving target search. In: IJCAI, pp. 615–620 (2009)
Sun, X., Yeoh, W., Koenig, S.: Generalized Fringe-Retrieving A*: Faster Moving Target Search on State Lattices. In: AAMAS, pp. 1081–1088 (2010)
Sun, X., Yeoh, W., Uras, T., Koenig, S.: Incremental ARA*: An Incremental Anytime Search Algorithm for Moving Target Search. In: ICAPS (2012)
Likhachev, M., Gordon, M., Thrun, S.: ARA*: Anytime a* with provable bounds on sub-optimality. In: NIPS (2003)
Finke, R., Nilsson, N.: STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 3-4(2), 189–208 (1971)
Hoffmann, J., Nebel, B.: The FF Planning System: Fast Plan Generation Through Heuristic Search. JAIR 14(1), 253–302 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Pellier, D., Fiorino, H., Métivier, M. (2014). Planning When Goals Change: A Moving Target Search Approach. In: Demazeau, Y., Zambonelli, F., Corchado, J.M., Bajo, J. (eds) Advances in Practical Applications of Heterogeneous Multi-Agent Systems. The PAAMS Collection. PAAMS 2014. Lecture Notes in Computer Science(), vol 8473. Springer, Cham. https://doi.org/10.1007/978-3-319-07551-8_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-07551-8_20
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07550-1
Online ISBN: 978-3-319-07551-8
eBook Packages: Computer ScienceComputer Science (R0)