Semi-autonomous Planning: A novel approach for plan segmentation in multiagent planning
Resumo
Este artigo apresenta uma extensão ao planejador HEART, que possui um mecanismo para resoluver problemas de planejamento através de rede de tarefas hierárquicas e ordenação parcial controlada por vínculos causais, permitindo planos intermediários. Esta extensão é uma ferramenta que permite seu uso em ambiente multiagente distribuído aproveitando desta capacidade de geração de subproblemas, permitindo que agentes de menor capacidade possam auxiliar na resolução de problemas mais complexos sem sacrificar a execução em tempo real. Para tanto é apresentado um novo tipo de falha, denominada falha de atribuição externa, e é provado que sua inclusão mantém a corretude e completude do planejador.
Referências
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.
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.
Publicado
28/11/2022
Como Citar
PEREIRA, Cassio H. M. P..
Semi-autonomous Planning: A novel approach for plan segmentation in multiagent planning. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 19. , 2022, Campinas/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 222-233.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2022.227316.
