Hierarchical semantic AI planning for human-like high-level multi-robot task execution

다국어 초록 (Multilingual Abstract)

Multi-robot systems are increasingly being utilized across various fields, leveraging robots working in parallel to allocate tasks and collaborate in mission execution. These systems need to solve the complex problem of planning missions that simultaneously consider the movements of individual robots and changes in the whole system. Researchers have proposed various systems for modeling and planning multi-robot tasks to address these challenges. Significantly, the introduction of semantic knowledge, such as environmental factors and domain rules, has suggested advanced approaches for high-level mission planning.
In this paper, we propose a multi-robot system that performs semantic knowledge-based high-level tasks. We define the semantic knowledge of multi-robot systems, considering the influences and interactions among environmental elements. To avoid redundancy in environments where multiple robots operate, we describe relationship knowledge between environmental elements, such as spatial occupancy and thing ownership, and model the actions and tasks that encompass this knowledge. Additionally, we define knowledge attributes to represent the hierarchical information of each space. The task planner groups robots according to their operational domains based on proposed semantic knowledge and rules, and generates high-level task plans for each group. This approach enables efficient planning of complex missions while addressing issues of overlap and deadlock among multiple robots. Through experimentation, we have validated the feasibility of the proposed semantic knowledge and demonstrated that the task planner can reduce planning time in a simulation environment. Finally, we applied the proposed system to perform multi-robot high-level missions to verify the practicality of the proposed semantic knowledge-based multi-robot system.

국문 초록 (Abstract)

여러 로봇을 병렬로 배치하여 작업을 할당하고 협업을 통해 임무를 수행하는 멀티 로봇 시스템이 다양한 분야에서 점점 더 많이 활용되고 있습니다. 이러한 시스템은 임무 계획 시 개별 로봇의 움직임과 전체 로봇의 영향을 동시에 고려해야 하는 복잡한 문제를 해결해야 합니다. 이러한 과제를 해결하기 위해 연구자들은 다중 로봇 작업을 모델링하고 계획하기 위한 다양한 시스템을 제안했습니다. 특히 환경 요인 및 도메인 규칙과 같은 시맨틱 지식의 도입으로 고수준 임무 계획을 위한 고도화된 방식이 제시되기도 했습니다. 본 논문에서는 시맨틱 지식 기반 고수준의 동작을 수행하는 다중 로봇 시스템을 제안합니다. 환경 요소 간의 영향과 상호작용을 고려하여 다중 로봇 시스템의 의미론적 지식을 정의합니다. 여러 로봇이 작동하는 환경에서 중복을 피하기 위해 공간 점유 및 객체 소유권과 같은 환경 요소 간의 관계에 대한 지식을 표현하고 이지식을 포괄하는 작업과 작업을 모델링합니다. 또한 각 공간의 계층적 정보를 표현하기 위해 지식 속성을 정의합니다. 작업 플래너는 제안된 시맨틱 지식과 규칙을 활용하여 공간 계층적 지식을 활용하고 로봇을 그룹화하여 각 그룹에 대한 최적의 작업 계획을 생성합니다. 이러한 접근 방식을 통해 여러 로봇 간의 중복 및 교착 문제를 해결하면서 복잡한 임무를 효율적으로 계획할 수 있습니다. 실험을 통해 제안한 시맨틱 지식의 타당성을 검증하고 시뮬레이션 환경에서 태스크 플래너가 계획 시간을 단축할 수 있음을 입증했습니다. 마지막으로 제안하는 시스템을 응용하여 다중 로봇의 고수준 미션을 수행하여 제안하는 의미지식 기반 다중로봇 시스템의 실용성을 검증했습니다.

목차 (Table of Contents)

• Chapter 1. Introduction 1
• Chapter 2. Related Work 7
• Chapter 3. Semantic Knowledge Modeling for Multi-robot System 16
• 3.1. Semantic Knowledge for Advanced Robot System 16
• 3.2. Semantic Knowledge Modeling for Multi-robot System 19
• 3.2.1. Relation Knowledge Modeling 19
• 3.2.2. TOSM-based Environment Element Modeling 23
• 3.3. Reasoning Rule Modeling for Multi-robot System 28
• Chapter 4. Semantic Knowledge-based Hierarchical Task Modeling 33
• 4.1. Hierarchy Task Modeling with Semantic Knowledge 33
• 4.1.1. Task Modeling for Hierarchical Planning Structure 33
• 4.1.2. PDDL Representation of Hierarchy Tasks 36
• 4.1.2.1. Semantic Knowledge-based Mission-level Tasks 37
• 4.1.2.2. Semantic Knowledge-based Coarse-level Tasks 39
• 4.1.2.3. Semantic Knowledge-based Fine-level Tasks 43
• Chapter 5. Hierarchical Semantic AI Planning for Multi-robot Task Execution 47
• 5.1. Overview 47
• 5.2. Hierarchical Planning Approach for Multi-robot 52
• 5.2.1. Task Planning 52
• 5.2.2. Task Re-planning 60
• 5.2.3. TOSM-based Autonomous Navigation 63
• 5.2.3.1. Robot Software Structure 63
• 5.2.3.2. TOSM-based Localization 65
• 5.2.3.3. TOSM-based Path Planning 73
• Chapter 6. Experiment 76
• 6.1. Experimental Environments 77
• 6.2. Experimental Scenarios 78
• 6.2.1. Semantic Knowledge-based Multi-robot Planning 78
• 6.2.2. Multi-robot Mission Planning 81
• 6.3. Experimental Results 85
• 6.3.1. Semantic Knowledge Test 85
• 6.3.1.1. Relationship Knowledge of Place 85
• 6.3.1.2. Relationship Knowledge of Object 89
• 6.3.1.3. Knowledge of Task 92
• 6.3.1.4. Discussion 94
• 6.3.2. Multi-robot Mission Planning 97
• 6.3.2.1. Task Planning 97
• 6.3.2.2. Task Re-planning 108
• 6.3.2.3. Discussion 114
• 6.4. Applications 115
• 6.4.1. Warehouse Scenario 116
• 6.4.1.1. Environment 116
• 6.4.1.2. Result 117
• 6.4.2. Campus Scenario 120
• 6.4.2.1. Environment 120
• 6.4.2.2. Result 124
• 6.4.3. ACS Scenario 128
• 6.4.3.1. Environment 128
• 6.4.3.2. Result 133
• Chapter 7. Conclusion 135
• References 139
• 논문요약 144

참고문헌 (Reference)

1. Planning algorithms, S. M. LaValle, Cambridge university press, , 2006

2. Summary of agv path planning,, J. Mao, C. Wang and, in 2019 3rd International Conference on Electronic Information Technology and Computer Engineering (EITCE), pp. 332–335, , 2019

3. Generating project networks, in, A. Tate, Proceedings of the 5th international joint conference on Artificial intelligenceVolume 2, 1977, pp. 888–893, , 1977

4. Owl web ontology language reference, M. Dean et al., vol. 10, no. February, 2004, , 2004

5. Forwardchaining partialorder planning, A. I. A. J. Coles, M. Fox and, D. Long, A. I. A. J. Coles, ICAPS 2010 Proc. 20th Int. Conf. Autom. Plan. Sched., no. Icaps, pp. 42–49, , 2010

6. Robot task planning using semantic maps, J. A. FernándezMadrigal, C. Galindo, A. Saffiotti, J. González and, Rob. Auton. Syst., vol. 56, no. 11, pp. 955–966, , 2008

7. Suma++: Efficient lidarbased semantic slam, J. Behley and, X. Chen, A. Milioto, C. Stachniss, E. Palazzolo, P. Giguere, in 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4530–4537, , 2019

8. Multirobotbased intelligent security system, K.L. Su, Y.L. Liao and, Artif. Life Robot., vol. 16, pp. 137–141, , 2011

9. Behaviorbased multirobot collision avoidance, A. Kleiner and, D. Sun, B. Nebel, in 2014 IEEE international conference on robotics and automation (ICRA), pp. 1668–1673, , 2014

10. A singleagent approach to multiagent planning, M. Crosby, M. Rovatsos, A. Jonsson and, Front. Artif. Intell. Appl., vol. 263, pp. 237–242, , 2014

11. Adaptivetaskplanningformulti-robotsmartwarehouse, A. BoluandÖ. Korçak, IEEE Access, vol. 9, pp. 27346–27358, , 2021

12. Monotone piecewise rational cubic interpolation,, M. Sarfraz, M. Z. Hussain and, Int. J. Comput. Math., vol. 86, no. 3, pp. 423–430, , 2009

13. An overview of hierarchical task network planning, M. Aiello, I. Georgievski and, arXiv Prepr. arXiv1403.7426, , 2014

14. Semantic information for robot navigation: A survey, J. Crespo, R. Barber, O. M. Mozos and, J. C. Castillo, vol. 10, no. 2, , 2020

15. Marketbased Multirobot coordination with HTN planning, S. Lacroix and, E. Chauveau, A. Milot, C. Lesire, in 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2606– 2612, , 2021

16. Leading the way: An efficient multirobot guidance system, in, P. Stone, S. Barrett and, P. Khandelwal, Proceedings of the 2015 international conference on autonomous agents and multiagent systems, pp. 1625–1633, , 2015

17. Decentralized prioritized planning in large multirobot teams,, K. Sycara and, P. Velagapudi, P. Scerri, in 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4603–4609, , 2010

18. ODSBot: Mobile Robot Navigation for Outdoor Delivery Services, J. Lee et al., IEEE Access, vol. 10, pp. 107250–107258, , 2022

19. Robot task planning and explanation in open and uncertain worlds, M. Hanheide et al., Artif. Intell., vol. 247, pp. 119–150, , 2017

20. Humanmultirobot team collaboration for efficient warehouse operation, A. Noa, O. Maksimov and, S. Kraus, A. Rosenfeld, Auton. Robot. Multirobot Syst., , 2016

21. Trajectory planning for multirobot systems: Methods and applications, D. Mart\’\in and, Á. Madridano, A. de la Escalera, A. AlKaff, Expert Syst. Appl., vol. 173, p. 114660, , 2021

22. Towards MultiRobot TaskMotion Planning for Navigation in Belief Space, M. Baglietto, F. Mastrogiovanni and, A. Thomas, arXiv Prepr. arXiv2010.00780, , 2020

23. Planning paths for package delivery in heterogeneous multirobot teams,, N. Mathew, S. L. Waslander, S. L. Smith and, IEEE Trans. Autom. Sci. Eng., vol. 12, no. 4, pp. 1298–1308, , 2015

24. PDDL2. 1: An extension to PDDL for expressing temporal planning domains, D. Long, M. Fox and, J. Artif. Intell. Res., vol. 20, pp. 61–124, , 2003

25. KnowRob: A knowledge processing infrastructure for cognitionenabled robots, M. Tenorth and, M. Beetz, vol. 32, no. 5, pp. 566–590, , 2013

26. SegMap: Segmentbased mapping and localization using datadriven descriptors, R. Dube et al., vol. 39, no. 2–3, pp. 339–355, , 2020

27. Path planning and intelligent scheduling of multiAGV systems in workshop, in, Y. Li and, X. Bai, J. Tan, H. Zhao, C. Liu, 2017 36th Chinese Control Conference (CCC), pp. 2735–2739, , 2017

28. A complete and scalable strategy for coordinating multiple robots within roadmaps, C. M. Clark and, J. McPhee, M. Peasgood, IEEE Trans. Robot., vol. 24, no. 2, pp. 283–292, , 2008

29. Plugin FrameworkBased NeuroSymbolic Grounded Task Planning for MultiAgent System,, J. Moon, Sensors, vol. 21, no. 23, p. 7896, , 2021

30. Assignment algorithms for modeling resource contention in multirobot task allocation, C. Nam and, D. A. Shell, IEEE Trans. Autom. Sci. Eng., vol. 12, no. 3, pp. 889–900, , 2015

31. Intelligent planning and control for multirobot coordination: An eventbased approach, N. Xi, T.J. Tarn and, A. K. Bejczy, IEEE Trans. Robot. Autom., vol. 12, no. 3, pp. 439–452, , 1996

32. Pddl planning with natural languagebased scene understanding for uavugv cooperation,, J. Moon and, B.H. Lee, vol. 9, no. 18, p. 3789, , 2019

33. Task Allocation of Intelligent Warehouse Picking System based on Multirobot Coalition., Q. Su and, F. Xue, H. Tang, T. Li, KSII Trans. Internet Inf. Syst., vol. 13, no. 7, , 2019

34. 3D dynamic scene graphs: Actionable spatial perception with places, objects, and humans, M. Abate, A. Gupta, J. Shi and, A. Rosinol, L. Carlone, arXiv Prepr. arXiv2002.06289, , 2020

35. Ontologybased multilayered robot knowledge framework (OMRKF) for robot intelligence, in, W. Hwang, G. H. Lim, Y.T. Park, J.H. Choi and, I. H. Suh, H. Suh, 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 429–436, , 2007

36. Centralized Task Allocation and Alignment Based on Constraint Table and Alignment Rules,, N. E. Hwang, H. J. Kim and, J. G. Kim, vol. 12, no. 13, p. 6780, , 2022

37. Optimized simultaneous conflictfree task assignment and path planning for multi AGV systems,, C. Secchi and, C. Fantuzzi, L. Sabattini, V. Digani, 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1083–1088, , 2017

38. A mechanism for scheduling multi robot intelligent warehouse system face with dynamic demand,, R. Y. Zhong and, A. V. Barenji, J. Jiang, G. Xu, Z. Li, vol. 31, pp. 469–480, , 2020

39. ALLIANCE: An Architecture for Fault Tolerant, Cooperative Control of Heterogeneous Mobile Robots, L. E. Parker, Engineering, , 1997

40. Autonomous navigation framework for intelligent robots based on a semantic environment modeling,, S. H. Joo et al., Appl. Sci., vol. 10, no. 9, pp. 1–30, , 2020

41. Ontologybased knowledge representation in robotic systems: A survey oriented toward applications, S. Manzoor et al., vol. 11, no. 10, p. 4324, , 2021

42. Control architecture concepts and properties of an ontology devoted to exchanges in mobile robotics, in, S. Dhouib et al., 6th National Conference on Control Architectures of Robots, pp. 24p, , 2011

43. Robotic delivery service in combined outdoorindoor environments: technical analysis and user evaluation, R. Esposito, R. Limosani, F. Cavallo and, G. Teti, A. Manzi, P. Dario, Rob. Auton. Syst., vol. 103, pp. 56–67, , 2018

44. Simultaneous task allocation and planning for temporal logic goals in heterogeneous multirobot systems,, P. Schillinger, M. Bürger and, D. V Dimarogonas, vol. 37, no. 7, pp. 818–838, , 2018

45. Distributed Multi Mobile Robot Path Planning and Obstacle Avoidance Based on ACO DWA in Unknown Complex Terrain,, Q. Wang, Z. Yang, J. Li, G. Xia, P. Li and, L. Yang, Electronics, vol. 11, no. 14, p. 2144, , 2022

46. A decentralized control strategy for resilient connectivity maintenance in multirobot systems subject to failures, in, C. H. C. Ribeiro and, C. Ghedini, L. Sabattini, Distributed Autonomous Robotic Systems: The 13th International Symposium, pp. 89–102, , 2018

47. FLMTSP: a fuzzy logic approach to solve the multiobjective multiple traveling salesman problem for multirobot systems, S. Trigui, A. Koubaa, U. Baroudi and, H. Youssef, O. Cheikhrouhou, Soft Comput., vol. 21, pp. 7351–7362, , 2017

48. A Flexible Semantic Ontological Model Framework and Its Application to Robotic Navigation in Large Dynamic Environments,, S. Joo et al., Electronics, vol. 11, no. 15, p. 2420, , 2022

49. A realtime autonomous robot navigation framework for human like highlevel interaction and task planning in global dynamic environment, H. Lee and, S. Manzoor, S. Joo, T.Y. Kuc, Y. G. Rocha, arXiv Prepr. arXiv1905.12942, , 2019