A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees
Multi-agent path finding (MAPF) is a classical NP-hard problem that considers planning collision-free paths for multiple agents simultaneously. A MAPF problem is typically solved via addressing a sequence of single-agent path finding subproblems in which well-studied algorithms such as A⁎ are applic...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/174651 |
| _version_ | 1811679871374458880 |
|---|---|
| author | He, Xiaoyu Tang, Xueyan Cai, Wentong Li, Jingning |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering He, Xiaoyu Tang, Xueyan Cai, Wentong Li, Jingning |
| author_sort | He, Xiaoyu |
| collection | NTU |
| description | Multi-agent path finding (MAPF) is a classical NP-hard problem that considers planning collision-free paths for multiple agents simultaneously. A MAPF problem is typically solved via addressing a sequence of single-agent path finding subproblems in which well-studied algorithms such as A⁎ are applicable. Existing methods based on this idea, however, rely on an exhaustive search and therefore only have asymptotic performance guarantees. In this article, we provide a modeling paradigm that converts a MAPF problem into a stochastic process and adopts a confidence bound based rule for finding the optimal state transition strategy. A randomized algorithm is proposed to solve this stochastic process, which combines ideas from conflict based search and Monte Carlo tree search. We show that the proposed method is almost surely optimal while enjoying non-asymptotic performance guarantees. In particular, the proposed method can, after solving N single-agent subproblems, produce a feasible solution with suboptimality bounded by O(1/N). The theoretical results are verified by several numerical experiments based on grid maps. |
| first_indexed | 2024-10-01T03:16:02Z |
| format | Journal Article |
| id | ntu-10356/174651 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:16:02Z |
| publishDate | 2024 |
| record_format | dspace |
| spelling | ntu-10356/1746512024-04-12T15:37:24Z A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees He, Xiaoyu Tang, Xueyan Cai, Wentong Li, Jingning School of Computer Science and Engineering Singtel Cognitive and Artificial Intelligence Lab for Enterprises (SCALE@NTU) Computer and Information Science Multi-agent path finding Non-asymptotic performance Multi-agent path finding (MAPF) is a classical NP-hard problem that considers planning collision-free paths for multiple agents simultaneously. A MAPF problem is typically solved via addressing a sequence of single-agent path finding subproblems in which well-studied algorithms such as A⁎ are applicable. Existing methods based on this idea, however, rely on an exhaustive search and therefore only have asymptotic performance guarantees. In this article, we provide a modeling paradigm that converts a MAPF problem into a stochastic process and adopts a confidence bound based rule for finding the optimal state transition strategy. A randomized algorithm is proposed to solve this stochastic process, which combines ideas from conflict based search and Monte Carlo tree search. We show that the proposed method is almost surely optimal while enjoying non-asymptotic performance guarantees. In particular, the proposed method can, after solving N single-agent subproblems, produce a feasible solution with suboptimality bounded by O(1/N). The theoretical results are verified by several numerical experiments based on grid maps. Ministry of Education (MOE) Submitted/Accepted version This study is supported under the RIE2020 Industry Alignment Fund – Industry Collaboration Projects (IAF-ICP) Funding Initiative, as well as cash and in-kind contribution from Singapore Telecommunications Limited (Singtel), through Singtel Cognitive and Artificial Intelligence Lab for Enterprises (SCALE@NTU). Xiaoyu He is also partially supported by the National Natural Science Foundation of China (62006252). Xueyan Tang is also partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 (Award MOE-T2EP20122-0007). 2024-04-07T01:25:37Z 2024-04-07T01:25:37Z 2024 Journal Article He, X., Tang, X., Cai, W. & Li, J. (2024). A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees. Artificial Intelligence, 329, 104084-. https://dx.doi.org/10.1016/j.artint.2024.104084 0004-3702 https://hdl.handle.net/10356/174651 10.1016/j.artint.2024.104084 2-s2.0-85183995426 329 104084 en MOE-T2EP20122-0007 Artificial Intelligence © 2024 Elsevier B.V. All rights reserved. This article may be downloaded for personal use only. Any other use requires prior permission of the copyright holder. The Version of Record is available online at http://doi.org/10.1016/j.artint.2024.104084. application/pdf |
| spellingShingle | Computer and Information Science Multi-agent path finding Non-asymptotic performance He, Xiaoyu Tang, Xueyan Cai, Wentong Li, Jingning A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees |
| title | A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees |
| title_full | A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees |
| title_fullStr | A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees |
| title_full_unstemmed | A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees |
| title_short | A stochastic process approach for multi-agent path finding with non-asymptotic performance guarantees |
| title_sort | stochastic process approach for multi agent path finding with non asymptotic performance guarantees |
| topic | Computer and Information Science Multi-agent path finding Non-asymptotic performance |
| url | https://hdl.handle.net/10356/174651 |
| work_keys_str_mv | AT hexiaoyu astochasticprocessapproachformultiagentpathfindingwithnonasymptoticperformanceguarantees AT tangxueyan astochasticprocessapproachformultiagentpathfindingwithnonasymptoticperformanceguarantees AT caiwentong astochasticprocessapproachformultiagentpathfindingwithnonasymptoticperformanceguarantees AT lijingning astochasticprocessapproachformultiagentpathfindingwithnonasymptoticperformanceguarantees AT hexiaoyu stochasticprocessapproachformultiagentpathfindingwithnonasymptoticperformanceguarantees AT tangxueyan stochasticprocessapproachformultiagentpathfindingwithnonasymptoticperformanceguarantees AT caiwentong stochasticprocessapproachformultiagentpathfindingwithnonasymptoticperformanceguarantees AT lijingning stochasticprocessapproachformultiagentpathfindingwithnonasymptoticperformanceguarantees |