Semi-autonomous Planning: A novel approach for plan segmentation in multiagent planning

• Cassio H. M. P. Pereira UFPR

DOI: https://doi.org/10.5753/eniac.2022.227316

Abstract

This article presents an extension to the HEART planner, which has a mechanism to solve planning problems by using hierarchical task networks and partial ordering controlled by causal links that allows intermediate plans. This extension introduces a tool that allows for the usage of the planner in the distributed multiagent environment by exploiting that capability for creating subproblems, allowing less capable agents to help solve higher complexity problems without sacrificing the real-time execution. For that end it is presented a new type of flaw, noted external attribution flaw, and it is proven that its inclusion maintains the planner properties of soundness and completeness.

References

Alford, R., Shivashankar, V., Roberts, M., Frank, J., and Aha, D. W. (2016). Hierarchical planning: Relating task and goal decomposition with task sharing. In IJCAI, pages 3022-3029.

Barrett, A. and Weld, D. S. (1994). Partial-order planning: evaluating possible efficiency gains. Artificial Intelligence, 67(1):71-112.

Behnke, G., Bercher, P., Biundo-Stephan, S., Glimm, B., Ponomaryov, D. K., and Schiller, M. R. G. (2015). Integrating ontologies and planning for cognitive systems. In Description Logics.

Bonet, B. and Geffner, H. (2000). Planning with incomplete information as heuristic search in belief space. In Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, pages 52-61. AAAI Press.

Boutilier, C., Dean, T., and Hanks, S. (1999). Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11(1):94.

Contreras-Cruz, M. A., Lopez-Perez, J. J., and Ayala-Ramirez, V. (2017). Distributed path planning for multi-robot teams based on artificial bee colony. In 2017 IEEE Congress on Evolutionary Computation (CEC), pages 541-548. IEEE.

Durfee, E. H. (2001). Distributed problem solving and planning. In ECCAI Advanced Course on Artificial Intelligence, pages 118-149. Springer.

Erol, K., Hendler, J., and Nau, D. S. (1994). HTN planning: Complexity and expressivity. In AAAI, volume 94, pages 1123-1128.

Fox, M. and Long, D. (2003). PDDL2. 1: An extension to PDDL for expressing temporal planning domains. Journal of artificial intelligence research.

Ghallab, M., Nau, D., and Traverso, P. (2004). Automated Planning: theory and practice. Elsevier.

Ghallab, M., Nau, D., and Traverso, P. (2014). The actor's view of automated planning and acting: A position paper. Artificial Intelligence, 208:1-17.

Ghallab, M., Nau, D., and Traverso, P. (2016). Automated planning and acting. Cambridge University Press.

Godoy, J., Karamouzas, I., Guy, S. J., and Gini, M. L. (2016). Implicit coordination in crowded multi-agent navigation. In 30th AAAI Conference on Artificial Intelligence, AAAI 2016, pages 2487-2493. AAAI press.

Gréa, A., Matignon, L., and Aknine, S. (2018). HEART: HiErarchical Abstraction for Real-Time Partial Order Causal Link Planning. In 1st Workshop on Hierarchical Planning at 28th International Conference on Automated Planning and Scheduling (ICAPS), pages 17-25.

Grea, A., Matignon, L., and Aknine, S. (2018). How explainable plans can make planning faster. In Workshop on Explainable Artificial Intelligence, pages 58-64.

Hernández, C. and Baier, J. A. (2012). Avoiding and escaping depressions in real-time heuristic search. Journal of Artificial Intelligence Research, 43:523-570.

Hoang, H., Lee-Urban, S., and Muñoz-Avila, H. (2005). Hierarchical plan representations for encoding strategic game ai. In Proceedings of the First AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, pages 63-68. AAAI Press.

Höller, D., Bercher, P., Behnke, G., and Biundo, S. (2018). Htn plan repair using unmodified planning systems. In Proc. of the First ICAPS Workshop on Hierarchical Planning, pages 26-30.

Jennings, N. R. (1999). Agent-based computing: Promise and perils. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, pages 1429-1436. Morgan Kaufmann Publishers Inc.

Knight, S., Rabideau, G., Chien, S., Engelhardt, B., and Sherwood, R. (2001). Casper: Space exploration through continuous planning. IEEE Intelligent Systems, 16(5):70-75.

Korf, R. E. (1990). Real-time heuristic search. Artificial intelligence, 42(2-3):189-211.

Lotem, A. and Nau, D. S. (2000). New advances in GraphHTN: identifying independent subproblems in large HTN domains. In Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, pages 206-215. AAAI Press.

Penberthy, J. S. and Weld, D. S. (1992). Ucpop: a sound, complete, partial order planner for adl. In Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, pages 103-114. Morgan Kaufmann Publishers Inc.

Rabideau, G., Knight, R., Chien, S., Fukunaga, A., and Govindjee, A. (1999). Iterative repair planning for spacecraft operations using the ASPEN system. In Artificial Intelligence, Robotics and Automation in Space, volume 440, page 99.

Sacerdoti, E. D. (1975). The nonlinear nature of plans. Technical report, Stanford Research Institute.

Sreedharan, S., Srivastava, S., Smith, D., and Kambhampati, S. (2019). Why can't you do that hal? explaining unsolvability of planning tasks. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 1422-1430. AAAI Press.

Weld, D. S. (1994). An introduction to least commitment planning. AI magazine, 15(4):27-27.

Winikoff, M., Dignum, V., and Dignum, F. (2018). Why bad coffee? explaining agent plans with valuings. In International Conference on Computer Safety, Reliability, and Security, pages 521-534. Springer.