A coordinated scheduling approach for task assignment and multi-agent path planning
Path finding is an essential problem in multi-agent systems, widely employed in warehousing and logistics. However, most of the current studies focus on the problem of assigning one agent with one task in a period, which may hinder the efficiency of path planning of the systems when facing multi-tas...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-01-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1319157824000193 |
| _version_ | 1827356716402999296 |
|---|---|
| author | Chengyuan Fang Jianlin Mao Dayan Li Ning Wang Niya Wang |
| author_facet | Chengyuan Fang Jianlin Mao Dayan Li Ning Wang Niya Wang |
| author_sort | Chengyuan Fang |
| collection | DOAJ |
| description | Path finding is an essential problem in multi-agent systems, widely employed in warehousing and logistics. However, most of the current studies focus on the problem of assigning one agent with one task in a period, which may hinder the efficiency of path planning of the systems when facing multi-tasks. To address this problem, we propose a multi-layer planner, under which a co-scheduling method for multi-agent with batch tasks and path planning in a continuous workspace is proposed. In the task allocation layer of the framework, a standard Genetic Algorithm (GA) is adopted, which optimizes the allocation of task sets, and minimizes the path lengths and the probability of conflicts. Secondly, an Improved Car-Like Conflict-Based Search (ICL-CBS) algorithm is presented as the conflict resolution layer to reduce the runtime. Finally, ICL-CBS and the Spatiotemporal Hybrid-State A* (SHA*) algorithm are jointly used to determine multi-agent paths in the path planning layer. We conduct experiments and compare our method with the baseline algorithm on random obstacles and practical scenarios. The results show that our method effectively improves the efficiency of multi-task completion, and alleviates the computational burden of underlying path planning. Specifically, our method has less runtime. |
| first_indexed | 2024-03-08T05:13:59Z |
| format | Article |
| id | doaj.art-3e8857c19a644cd9b8f2fe416242c3c8 |
| institution | Directory Open Access Journal |
| issn | 1319-1578 |
| language | English |
| last_indexed | 2024-03-08T05:13:59Z |
| publishDate | 2024-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj.art-3e8857c19a644cd9b8f2fe416242c3c82024-02-07T04:44:01ZengElsevierJournal of King Saud University: Computer and Information Sciences1319-15782024-01-01361101930A coordinated scheduling approach for task assignment and multi-agent path planningChengyuan Fang0Jianlin Mao1Dayan Li2Ning Wang3Niya Wang4Kunming University of Science and Technology, ChinaKunming University of Science and Technology, ChinaCorresponding author.; Kunming University of Science and Technology, ChinaKunming University of Science and Technology, ChinaKunming University of Science and Technology, ChinaPath finding is an essential problem in multi-agent systems, widely employed in warehousing and logistics. However, most of the current studies focus on the problem of assigning one agent with one task in a period, which may hinder the efficiency of path planning of the systems when facing multi-tasks. To address this problem, we propose a multi-layer planner, under which a co-scheduling method for multi-agent with batch tasks and path planning in a continuous workspace is proposed. In the task allocation layer of the framework, a standard Genetic Algorithm (GA) is adopted, which optimizes the allocation of task sets, and minimizes the path lengths and the probability of conflicts. Secondly, an Improved Car-Like Conflict-Based Search (ICL-CBS) algorithm is presented as the conflict resolution layer to reduce the runtime. Finally, ICL-CBS and the Spatiotemporal Hybrid-State A* (SHA*) algorithm are jointly used to determine multi-agent paths in the path planning layer. We conduct experiments and compare our method with the baseline algorithm on random obstacles and practical scenarios. The results show that our method effectively improves the efficiency of multi-task completion, and alleviates the computational burden of underlying path planning. Specifically, our method has less runtime.http://www.sciencedirect.com/science/article/pii/S1319157824000193Multi-agent systemTask allocationMulti-agent path findingGenetic algorithm |
| spellingShingle | Chengyuan Fang Jianlin Mao Dayan Li Ning Wang Niya Wang A coordinated scheduling approach for task assignment and multi-agent path planning Journal of King Saud University: Computer and Information Sciences Multi-agent system Task allocation Multi-agent path finding Genetic algorithm |
| title | A coordinated scheduling approach for task assignment and multi-agent path planning |
| title_full | A coordinated scheduling approach for task assignment and multi-agent path planning |
| title_fullStr | A coordinated scheduling approach for task assignment and multi-agent path planning |
| title_full_unstemmed | A coordinated scheduling approach for task assignment and multi-agent path planning |
| title_short | A coordinated scheduling approach for task assignment and multi-agent path planning |
| title_sort | coordinated scheduling approach for task assignment and multi agent path planning |
| topic | Multi-agent system Task allocation Multi-agent path finding Genetic algorithm |
| url | http://www.sciencedirect.com/science/article/pii/S1319157824000193 |
| work_keys_str_mv | AT chengyuanfang acoordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning AT jianlinmao acoordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning AT dayanli acoordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning AT ningwang acoordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning AT niyawang acoordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning AT chengyuanfang coordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning AT jianlinmao coordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning AT dayanli coordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning AT ningwang coordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning AT niyawang coordinatedschedulingapproachfortaskassignmentandmultiagentpathplanning |