Одноагентный и мультиагентный поиск пути в меняющихся во времени средах / Single-Agent and Multi-Agent Path Finding In Time-Varying Environments тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Али Зейн Алабидин

• Али Зейн Алабидин
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Али Зейн Алабидин

Contents

Page

Introduction

Chapter 1. Path Finding in Time-Varying Environments

1.1 Basic Definitions

1.2 Single-Agent Path Finding in Dynamic Environment Problem

1.2.1 Problem Statement

1.2.2 Problem Hardness

1.2.3 Simplified Problem

1.2.4 Review on the Problem-Solving Methods

1.2.5 Contribution

1.3 Multi-Agent Path Finding problem

1.3.1 Problem Statement

1.3.2 Problem Hardness

1.3.3 Simplified Problem

1.3.4 Review on the Problem-Solving Methods

1.3.5 Contribution

1.4 Chapter Summary

Chapter 2. Single Agent Path Finding with Kinodynamic

Constraints in Dynamic Environments

2.1 Method

2.1.1 Background

2.1.2 Safe Interval Path Planning with Interval Projection

2.2 Theoretical Properties

2.3 Empirical Evaluation

2.3.1 Single-Agent In Dynamic Environment

2.3.2 Multi-Agents in Static Environment

2.4 Chapter Summary

Chapter 3. Makespan-Optimal Anonymous Multi-Agent Path

Finding

Page

3.1 Method

3.1.1 Background

3.1.2 Bulk Search

3.2 Theoretical Properties

3.3 Empirical Evaluation

3.4 Chapter Summary

Chapter 4. Optimal Anonymous Multi-Agent Path Finding

Problem with Disappearing Agents

4.1 Method

4.1.1 Background

4.1.2 Reduction to Minimum-Cost Maximum-Flow problem

4.1.3 Solving Minimum-Cost Maximum-Flow On The Introduced Networks

4.2 Theoretical Properties

4.3 Empirical Evaluation

4.4 Chapter Summary

Conclusion

List of figures

List of tables

Введение диссертации (часть автореферата) на тему «Одноагентный и мультиагентный поиск пути в меняющихся во времени средах / Single-Agent and Multi-Agent Path Finding In Time-Varying Environments»

Introduction

Relevance of the research topic. Mobile robots, drones, autonomous vehicles, virtual agents in video games need to plan their paths in order to move safely in the environment and accomplish their tasks. This problem attracts an increased attention among robotics and artificial intelligence communities recently due to the fact that more advanced and complex robots start working in highly-changing environments where many other objects are moving around. Some examples for such cases include industrial robots where they need to plan their trajectories among other robots and workers [1], delivery robots that have to navigate among people in the streets [2], cleaning robots that work in parks and should avoid other walkers while cleaning, etc.

Moreover, all moving objects in the environment might be controllable, and in such cases it is required to organize their movements simultaneously. This problem is known as multi-agent path finding. For example, in some video strategy games [3] it is required to move numerous agents from place to place considering different parameters inside the environment. Other examples include autonomous aircraft-towing vehicles [4], autonomous intersection management [5], forklift robot fleets [6], swarms of differential-drive robots and quadcopters [7—9].

In general, there are three important features for ideal solvers of path finding problems. First, the solver should account for the agent's (e.g., robot) constraints as much as possible in order for the produced solutions to be safely applicable in real-life applications (e.g., consider the offset in the real path for a kinodynamic robot which was planned assuming a simultaneous ability to stop/start moving). Second, the solver should be fast so the planning can be run in real-time so the agent is always capable to react and adapt with the environment changes in the real-time. Third, it is desirable for the solver to return optimal solutions such that producing paths which minimizes the travel time or the fuel cost, etc. Consider autonomous vehicles which always choose the optimal highways to deliver in the least time with full safety, warehouse robots where every reduced second in robot working time increases the overall throughput, etc.

In this dissertation, we aim at developing efficient algorithms which can produce feasible and optimal solutions in order to help pushing the progress in Robotics and Artificial Intelligence domains. Particularly, the dissertation includes

research in three problems in two main areas. The first problem is the problem of single-agent path finding in a known dynamic environment when the agent has kinodynamic constraints. The second and the third problem are two versions of the multi-agent path finding (MAPF) problem.

The degree of development of the topic. In general, solving the path finding problem in complex conditions consists roughly of two steps: defining the motion primitives which the agent can do w.r.t. its differential constraints and finding the sequence of motion primitives which lead the agent to its goal position. In the first step, the motion primitives can be represented in different ways (i.e., explicitly as sequence of points, implicitly as continuous functions, procedures to generate them from the forward agent model in either random or deterministic way, etc.) and using different methods. Some of these methods include steering functions, experimentally-produced motion primitives, forward model simulation, optimization methods. In some cases, the path is tried to be found directly from this step by trying to find a continuous function from the start to the end, e.g., using optimization methods [10; 11]. However, some of these methods are computationally expensive, and some other require an initial guess (a rough path which is found by another method) which highly affects the final solution and may lead to locally optimal results.

In the second step, the methods to find the sequence of moves include, among others, graph search, sampling-based incremental search, graph-based incremental search and machine learning methods. The sampling-bases incremental search, most famously random sampling [12], searches the goal point by sampling the free space and then growing the search tree toward the sample points until getting close to the goal point. This method is used usually for searching paths in high-dimensional spaces, however it generally produces rough paths with weak (e.g., probabilistic) guarantees regarding the completeness and optimality. Machine learning methods [13] such as supervised learning (SL) methods and reinforcement learning (RL) methods are useful to generate feasible actions (motion primitives) for the agent, however as a global searcher it has several disadvantages such as the dependence on training data for SL methods and the require of reward functions for RL methods. On the other hand, if the explicit graph of actions for the agent is given (or when the actions are given for each state of the agent implicitly), graph search (or graph-based incremental search) methods can be a suitable choice. Graph search methods explore the given actions deterministically, and therefore can in

most cases guarantee the completeness and the optimality of the returned solution (w.r.t. the input actions).

Considering the wide use of graph-based search methods and the strong deterministic guarantees they feature, this dissertation mainly focuses on developing new graph-based methods and enhancing existing ones. The dissertation is structured as follows. In the first chapter, we begin by defining the problems formally, presenting the current progress and stating our contribution. Next chapters are dedicated to explain our novel methods to solve the problems. Each chapter is organized as follows. It begins with an introductory background. Then, the novel method is explained theoretically and reinforced by proved theorems and pseudocodes. Finally, we show the practical performance of the presented methods through experimental tests.

Primary goals and objectives of the study is to research and develop the algorithms for solving path finding problems. In specific, the single-agent path finding problem in dynamic environment and the multi-agent path finding problem.

Tasks. Particularly, several algorithms were developed to achieve the goals of the dissertation, as follows:

1. Developing an algorithm to solve path finding problem for single agent when: Firstly, the agent has kinodynamic constraints i.e., limited maximum acceleration/deceleration. Secondly, the environments are populated with static and dynamic obstacles.

2. Developing an efficient algorithm to find paths for several agents simultaneously when the agents can interchange the goal positions.

3. Developing efficient method to find paths for several agents simultaneously when the agents can interchange the goal positions and the agents are assumed to leave the goal positions directly after arriving.

Scientific novelty: In completing the tasks set in the dissertation research, the following new scientific achievements were obtained:

1. A novel and efficient algorithm to optimally solve Path Finding problem in dynamic environments for single agent with kinodynamic constraints was presented and proved.

2. A novel and efficient algorithm was presented and proved to improve the existing algorithms which are used to optimally find paths for several agents when the agents can interchange the goal positions between each other.

3. Novel and efficient method was proposed and proved to optimally find paths for several agents when the agents can interchange the goal positions between each other, and the agents leave the goal positions after arriving. Additionally, an algorithm and improvement techniques were developed to solve the subtasks of the method efficiently.

The theoretical and practical value of the dissertation results is reflected in the formulated novel and efficient algorithms for solving specific path finding problems, with the accompanying theorems and code. The first proposed algorithm maintains the completeness and efficiency of the state-of-the-art heuristic search algorithms but can additionally account for the kinodynamic constraints of the agent. The second proposed algorithm boosts the process of finding solutions for anonymous multi-agent path finding problems. The third proposed algorithm provides a new way of finding solutions for the problem of anonymous multi-agent path finding problems with disappearing agents optimally and efficiently. The research problem is considered one of the core problems in Robotics Navigation research which is considered one of the most active researches in the Artificial Intelligence area in current times. The value of this research for other scientific groups is that the proposed algorithms present efficient solutions to three of the many faced path planning problems in this area. That is, the algorithms can be either used as a ready product for solving the problems efficiently in practice, or as a core for a future development in path planning solvers in general.

Research methods. The dissertation work uses methods of graph theory and logic. The efficiency of all methods presented in the dissertation was also assessed using empirical experiments. Experiments for all algorithms including competitors were conducted under the same conditions such as the hardware and the time availability, and on the same tests. All methods were implemented using C++ language.

Statements to be defended.

1. The developed algorithm to optimally solve Path Finding problem in dynamic environments for single agent with kinodynamic constraints. The formulated theorems to prove the optimality of the algorithm.

2. The developed algorithm to improve the existing algorithms which are used to optimally find paths for several agents when the agents can interchange the goal positions between each other. The formulated theorems to prove the optimality of the algorithm.

3. The developed method to optimally find paths for several agents when the agents can interchange the goal positions between each other, and the agents leave the goal positions after arriving. The algorithm and techniques proposed to efficiently solve the developed method. The formulated theorems to prove their optimality.

The validity and reliability of the results are confirmed by the correct and rigorous application of the methods of discrete mathematics and mathematical logic during the research, in particular, when proving the theoretical properties of the proposed algorithms. The reliability of the results is further ensured by the results of empirical experiments conducted using benchmarks obtained from open sources widely used in the scientific community in the field of single-agent and multi-agent planning. The validity and reliability of the results obtained during the study are additionally supported by the approbation of the results at leading scientific conferences and seminars in the field of automatic planning.

Approbation of work. The main results of the dissertation were presented at the following conferences:

1. The 38th AAAI Conference on Artificial Intelligence, Vancouver, Canada, 2024.

2. The 37th AAAI Conference on Artificial Intelligence, Washington DC, USA, 2023.

3. The VI All-Russian scientific and practical seminar on Artificial Intelligence For Unmanned Vehicles, Moscow, Russia, 2021.

4. The 6th International Conference On Interactive Collaborative Robotics, St. Petersburg, Russia, 2021.

Author's contribution. The author took an active part in research, in the preparation and presentation of papers and reports on the topic of the dissertation. The software implementation and testing of algorithms, conducting model experiments, as well as processing the results obtained were carried out by the author personally. The proofs of the theorems given in the dissertation belong to the author and have not been published before.

Publications The main results of the work were published in one K1 journal [116] and 2 [117; 118] printed proceedings of 2 scientific conferences, both are indexed in Scopus and have A* rank.

Volume and structure of the work. Dissertation consists of 4 chapter, conclusion and 0 appendices. The complete volume of the dissertation consists of 127 page, including 28 figure and 3 tables. Bibliography consists of 115 references.

Заключение диссертации по теме «Другие cпециальности», Али Зейн Алабидин

Conclusion

In many real-world applications, single or several agents need to move in their changing environments, and hence they need to plan for their paths before, in order to move safely and efficiently. When the environment is dynamically changing, planning for paths becomes more difficult as for every time moment, the environment may completely be updated. Taking the dynamic change into account while searching for a path, the time dimension should be added and the search space becomes extremely large. Therefore, in this dissertation, it was studied three real-world examples of path finding problems in dynamic (time-varying) environments where we show how we can overcome this difficulty. The three problems were solved by novel and efficient algorithms which always find optimal solutions with theoretical guarantees and empirical verification. The main results of the work are as follows:

1. The algorithm Safe Interval Path Planning with Interval Projection (SIPP-IP) to solve single-agent path finding problem for an agent with kinodynamic constraints moving in a known dynamic environment efficiently.

2. The algorithm Bulk-Search (BS) to solve the Anonymous Mutli-Agent Path Finding (AMAPF) problem efficiently.

3. The method of reducing Anonymous Multi-Agent Path Finding with Disappearing Agents (AMAPFD) problem to Minimum-Cost Maximum-Flow MCMF problem.

4. The extended BS algorithm (General Bulk Search GBS) algorithm to solve the reduced MCMF problem from AMAPFD efficiently.

In addition to that the algorithms have direct real-world applications (though simplified in some details), and the presented algorithms provide direct and efficient solutions to the problems, the used ideas, techniques, observations and heuristics have wider and open usage more in AI and robotics problems. That is, the technique and ideas used to compress the time dimensions in three different types of graphs and networks can potentially provide newer solutions for similar problems in analogous conditions. For example, the time dimension in SIPP-IP can be replaced by another dimension and the same techniques can be applied to compress the dimension and improve the search process. I quote a piece of the feedback given by one the AAAI

2023 conference reviewers for one of my papers: Given the wide application of the maxflow algorithm for AMAPF in various problems (TAPF, lifelong MAPD, etc.), this simple speedup technique has broad potential application.

Список литературы диссертационного исследования кандидат наук Али Зейн Алабидин, 2024 год

References

1. Wurman, P. R. Coordinating hundreds of cooperative, autonomous vehicles in warehouses [Text] / P. R. Wurman, R. D'Andrea, M. Mountz //AI magazine. — 2008. — Vol. 29, no. 1. — P. 9—9.

2. Yandex. Yandex.Rovers complete 1,500 autonomous deliveries [Text] / Yandex. — 2020. — https://ai.yandex.com/blog/rovers.

3. Vlassis, N. Strategic Games [Text] / N. Vlassis //A Concise Introduction to Multiagent Systems and Distributed Artificial Intelligence. — Cham : Springer International Publishing, 2007. — P. 15—21. —URL: https://doi.org/10.1007/ 978-3-031-01543-4_3.

4. Planning, scheduling and monitoring for airport surface operations [Text] / R. Morris [et al.] // Workshops at the Thirtieth AAAI Conference on Artificial Intelligence. — 2016.

5. Dresner, K. A multiagent approach to autonomous intersection management [Text] / K. Dresner, P. Stone // Journal of artificial intelligence research. — 2008. — Vol. 31. — P. 591—656.

6. Motion planning and goal assignment for robot fleets using trajectory optimization [Text] / J. Salvado [et al.] // 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — IEEE. 2018. — P. 7939—7946.

7. Yakovlev, K. Prioritized multi-agent path finding for differential drive robots [Text] / K. Yakovlev, A. Andreychuk, V. Vorobyev // Proceedings of the 2019 European Conference on Mobile Robots (ECMR 2019). — 2019. — P. 1—6.

8. Multi-agent path finding with kinematic constraints [Text] / W. Hönig [et al.] // Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 26. — 2016.

9. Trajectory planning for quadrotor swarms [Text] / W. Honig [et al.] // IEEE Transactions on Robotics. — 2018. — Vol. 34, no. 4. — P. 856—869.

10. Reshamwala, A. Robot path planning using an ant colony optimization approach: a survey [Text] / A. Reshamwala, D. P. Vinchurkar // International Journal of Advanced Research in Artificial Intelligence. — 2013. — Vol. 2, no. 3. — P. 65—71.

11. UAV path planning using optimization approaches: A survey [Text] / A. Ait Saadi [et al.] // Archives of Computational Methods in Engineering. — 2022. — Vol. 29, no. 6. — P. 4233—4284.

12. LaValle, S. Rapidly-exploring random trees: A new tool for path planning [Text] / S. LaValle // Research Report 9811. — 1998.

13. Otte, M. W. A survey of machine learning approaches to robotic path-planning [Text] / M. W. Otte // University of Colorado at Boulder. — 2015.

14. Reif, J. H. Complexity of the mover's problem and generalizations [Text] / J. H. Reif // 20th Annual Symposium on Foundations of Computer Science (sfcs 1979). — IEEE Computer Society. 1979. — P. 421—427.

15. LaValle, S. M. Planning algorithms [Text] / S. M. LaValle. — Cambridge university press, 2006.

16. Canny, J. New lower bound techniques for robot motion planning problems [Text] / J. Canny, J. Reif // 28th Annual Symposium on Foundations of Computer Science (sfcs 1987). — IEEE. 1987. — P. 49—60.

17. A survey of motion planning and control techniques for self-driving urban vehicles [Text] / B. Paden [et al.] // IEEE Transactions on intelligent vehicles. — 2016. — Vol. 1, no. 1. — P. 33—55.

18. Real-time motion planning with applications to autonomous urban driving [Text] / Y. Kuwata [et al.] // IEEE Transactions on control systems technology. — 2009. — Vol. 17, no. 5. — P. 1105—1118.

19. Hwan Jeon, J. Anytime computation of time-optimal off-road vehicle maneuvers using the RRT [Text] / J. Hwan Jeon, S. Karaman, E. Frazzoli // 2011 50th IEEE Conference on Decision and Control and European Control Conference. — IEEE. 2011. — P. 3276—3282.

20. LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics [Text] / A. Perez [et al.] // 2012 IEEE International Conference on Robotics and Automation. — IEEE. 2012. — P. 2537—2542.

21. Webb, D. J. Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics [Text] / D. J. Webb, J. Van Den Berg // 2013 IEEE international conference on robotics and automation. — IEEE. 2013. — P. 5054—5061.

22. Spline-based RRT path planner for non-holonomic robots [Text] / K. Yang [et al.] // Journal of Intelligent & Robotic Systems. — 2014. — Vol. 73, no. 1. — P. 763—782.

23. Palmieri, L. A novel RRT extend function for efficient and smooth mobile robot motion planning [Text] / L. Palmieri, K. O. Arras // 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. — IEEE. 2014. — P. 205—211.

24. Dubins, L. E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents [Text] / L. E. Dubins // American Journal of mathematics. — 1957. — Vol. 79, no. 3. — P. 497—516.

25. Reeds, J. Optimal paths for a car that goes both forwards and backwards [Text] / J. Reeds, L. Shepp // Pacific journal of mathematics. — 1990. — Vol. 145, no. 2. — P. 367—393.

26. LaValle, S. M. Randomized kinodynamic planning [Text] / S. M. LaValle, J. J. Kuffner Jr // The international journal of robotics research. — 2001. — Vol. 20, no. 5. — P. 378—400.

27. Frazzoli, E. Maneuver-based motion planning for nonlinear systems with symmetries [Text] / E. Frazzoli, M. A. Dahleh, E. Feron // IEEE transactions on robotics. — 2005. — Vol. 21, no. 6. — P. 1077—1091.

28. Making bertha drive—an autonomous journey on a historic route [Text] / J. Ziegler [et al.] // IEEE Intelligent transportation systems magazine. — 2014. — Vol. 6, no. 2. — P. 8—20.

29. A conjugate gradient-based BPTT-like optimal control algorithm with vehicle dynamics control application [Text] / J. Kasac [et al.] // IEEE Transactions on control systems technology. — 2010. — Vol. 19, no. 6. — P. 1587—1595.

30. Darby, C. L. An hp-adaptive pseudospectral method for solving optimal control problems [Text] / C. L. Darby, W. W. Hager, A. V. Rao // Optimal Control Applications and Methods. — 2011. — Vol. 32, no. 4. — P. 476—502.

31. Tassa, Y. Control-limited differential dynamic programming [Text] / Y. Tassa, N. Mansard, E. Todorov // 2014 IEEE International Conference on Robotics and Automation (ICRA). — IEEE. 2014. — P. 1168—1175.

32. Polak, E. An historical survey of computational methods in optimal control [Text] / E. Polak // SIAM review. — 1973. — Vol. 15, no. 2. — P. 553—584.

33. Betts, J. T. Survey of numerical methods for trajectory optimization [Text] / J. T. Betts // Journal of guidance, control, and dynamics. — 1998. — Vol. 21, no. 2. — P. 193—207.

34. Chazelle, B. Approximation and decomposition of shapes [Text] / B. Chazelle // Algorithmic and Geometric Aspects of Robotics. — 1985. — Vol. 1. — P. 145—185.

35. O'Dunlaing, C. A "retraction" method for planning the motion of a disc [Text] / C. O'Dunlaing, C. K. Yap // Journal of Algorithms. — 1985. — Vol. 6, no. 1. — P. 104—111.

36. Takahashi, O. Motion planning in a plane using generalized Voronoi diagrams [Text] / O. Takahashi, R. J. Schilling // IEEE Transactions on robotics and automation. — 1989. — Vol. 5, no. 2. — P. 143—150.

37. Nilsson, N. J. A mobius automation: An application of artificial intelligence techniques [Text] / N. J. Nilsson // Proceedings of the 1st international joint conference on Artificial intelligence, IJCAI. Vol. 69. — Citeseer. 1969. — P. 509—520.

38. Latombe, J.-C. Robot motion planning [Text]. Vol. 124 / J.-C. Latombe. — Springer Science & Business Media, 2012.

39. Schwartz, J. T. On the "piano movers" problem. II. General techniques for computing topological properties of real algebraic manifolds [Text] / J. T. Schwartz, M. Sharir // Advances in applied Mathematics. — 1983. — Vol. 4, no. 3. — P. 298—351.

40. Probabilistic roadmaps for path planning in high-dimensional configuration spaces [Text] / L. E. Kavraki [et al.] // IEEE transactions on Robotics and Automation. — 1996. — Vol. 12, no. 4. — P. 566—580.

41. Pivtoraiko, M. Kinodynamic motion planning with state lattice motion primitives [Text] / M. Pivtoraiko, A. Kelly //2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. — IEEE. 2011. — P. 2172—2179.

42. Kavraki, L. E. Analysis of probabilistic roadmaps for path planning [Text] / L. E. Kavraki, M. N. Kolountzakis, J.-C. Latombe // IEEE Transactions on Robotics and automation. — 1998. — Vol. 14, no. 1. — P. 166—171.

43. Karaman, S. Sampling-based algorithms for optimal motion planning [Text] / S. Karaman, E. Frazzoli // The international journal of robotics research. — 2011. — Vol. 30, no. 7. — P. 846—894.

44. Dijkstra, E. W. A note on two problems in connexion with graphs [Text] / E. W. Dijkstra // Edsger Wybe Dijkstra: His Life, Work, and Legacy. — 2022. — P. 287—290.

45. Hart, P. E. A formal basis for the heuristic determination of minimum cost paths [Text] / P. E. Hart, N. J. Nilsson, B. Raphael // IEEE transactions on Systems Science and Cybernetics. — 1968. — Vol. 4, no. 2. — P. 100—107.

46. Theta*: Any-angle path planning on grids [Text] / K. Daniel [et al.] // Journal of Artificial Intelligence Research. — 2010. — Vol. 39. — P. 533—579.

47. Phillips, M. SIPP: Safe interval path planning for dynamic environments [Text] / M. Phillips, M. Likhachev // Proceedings of The 2011 IEEE International Conference on Robotics and Automation (ICRA 2011). — 2011. — P. 5628—5635.

48. Multi-robot path planning for a swarm of robots that can both fly and drive [Text] / B. Araki [et al.] // 2017 IEEE International Conference on Robotics and Automation (ICRA). — IEEE. 2017. — P. 5575—5582.

49. Multi-agent pathfinding with continuous time [Text] / A. Andreychuk [et al.] // Artificial Intelligence. — 2022. — Vol. 305. — P. 103662.

50. Optimal and Bounded-Suboptimal Multi-Agent Motion Planning [Text] / L. Cohen [et al.] // Proceedings of the 12th Annual Symposium on Combinatorial Search (SOCS 2019). — 2019. — P. 44—51.

51. Yakovlev, K. Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [Text] / K. Yakovlev, A. Andreychuk // Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021). — 2021. — P. 405—414.

52. Narayanan, V. Anytime safe interval path planning for dynamic environments [Text] / V. Narayanan, M. Phillips, M. Likhachev // Proceedings of The 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2012). — 2012. — P. 4708—4715.

53. Yakovlev, K. Revisiting Bounded-Suboptimal Safe Interval Path Planning [Text] / K. Yakovlev, A. Andreychuk, R. Stern // Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020). — 2020. — P. 300—304.

54. Pohl, I. Heuristic search viewed as path finding in a graph [Text] / I. Pohl // Artificial intelligence. — 1970. — Vol. 1, no. 3/4. — P. 193—204.

55. Pearl, J. Studies in semi-admissible heuristics [Text] / J. Pearl, J. H. Kim // IEEE transactions on pattern analysis and machine intelligence. — 1982. — No. 4. — P. 392—399.

56. MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search [Text] / J. Li [et al.] // Proceedings of the AAAI Conference on Artificial Intelligence. — 2022.

57. Yakovlev, K. Any-angle pathfinding for multiple agents based on SIPP algorithm [Text] / K. Yakovlev, A. Andreychuk // Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 27. — 2017.

58. Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery [Text] / H. Ma [et al.] // Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019). — 2019. — P. 7651—7658.

59. The focussed D* algorithm for real-time replanning [Text] / A. Stentz [et al.] // IJCAI. Vol. 95. — 1995. — P. 1652—1659.

60. Koenig, S. Fast replanning for navigation in unknown terrain [Text] / S. Koenig, M. Likhachev // IEEE transactions on robotics. — 2005. — Vol. 21, no. 3. — P. 354—363.

61. Yu, J. Planning optimal paths for multiple robots on graphs [Text] / J. Yu, S. M. LaValle // 2013 IEEE International Conference on Robotics and Automation. — IEEE. 2013. — P. 3612—3617.

62. Surynek, P. An optimization variant of multi-robot path planning is intractable [Text] / P. Surynek // Proceedings of the AAAI conference on artificial intelligence. Vol. 24. — 2010. — P. 1261—1263.

63. Yu, J. Intractability of optimal multirobot path planning on planar graphs [Text] / J. Yu // IEEE Robotics and Automation Letters. — 2015. — Vol. 1, no. 1. — P. 33—40.

64. Banfi, J. Intractability of time-optimal multirobot path planning on 2D grid graphs with holes [Text] / J. Banfi, N. Basilico, F. Amigoni // IEEE Robotics and Automation Letters. — 2017. — Vol. 2, no. 4. — P. 1941—1947.

65. Surynek, P. Towards optimal cooperative path planning in hard setups through satisfiability solving [Text] / P. Surynek // Pacific Rim international conference on artificial intelligence. — Springer. 2012. — P. 564—576.

66. Yu, J. Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics [Text] / J. Yu, S. M. LaValle // IEEE Transactions on Robotics. — 2016. — Vol. 32, no. 5. — P. 1163—1177.

67. Gomez, R. N. Solving sum-of-costs multi-agent pathfinding with answer-set programming [Text] / R. N. Gómez, C. Hernández, J. A. Baier // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. — 2020. — P. 9867—9874.

68. A general formal framework for pathfinding problems with multiple agents [Text] / E. Erdem [et al.] // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 27. — 2013. — P. 290—296.

69. Modifying optimal SAT-based approach to multi-agent path-finding problem to suboptimal variants [Text] / P. Surynek [et al.] // Proceedings of the International Symposium on Combinatorial Search. Vol. 8. — 2017. — P. 169—170.

70. Surynek, P. Reduced Time-Expansion Graphs and Goal Decomposition for Solving Cooperative Path Finding Sub-Optimally. [Text] / P. Surynek // IJCAI. Vol. 15. — 2015. — P. 1916—1922.

71. A new constraint satisfaction perspective on multi-agent path finding: Preliminary results [Text] / J. Wang [et al.] // 18th International Conference on Autonomous Agents and Multi-Agent Systems. — 2019.

72. Han, S. D. Integer programming as a general solution methodology for path-based optimization in robotics: Principles, best practices, and applications [Text] / S. D. Han, J. Yu // 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — IEEE. 2019. — P. 1890—1897.

73. Luna, R. J. Push and swap: Fast cooperative path-finding with completeness guarantees [Text] / R. J. Luna, K. E. Bekris // Twenty-Second International Joint Conference on Artificial Intelligence. — 2011.

74. Sajid, Q. Multi-agent pathfinding with simultaneous execution of single-agent primitives [Text] / Q. Sajid, R. Luna, K. Bekris // Proceedings of the International Symposium on Combinatorial Search. Vol. 3. — 2012. — P. 88—96.

75. De Wilde, B. Push and rotate: cooperative multi-agent path planning [Text] / B. De Wilde, A. W. Ter Mors, C. Witteveen // Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems. — 2013. — P. 87—94.

76. Khorshid, M. A polynomial-time algorithm for non-optimal multi-agent pathfinding [Text] / M. Khorshid, R. Holte, N. Sturtevant // Proceedings of the International Symposium on Combinatorial Search. Vol. 2. — 2011. — P. 76—83.

77. Masehian, E. Solvability of multi robot motion planning problems on trees [Text] / E. Masehian, A. H. Nejad // 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems. — IEEE. 2009. — P. 5936—5941.

78. Surynek, P. A novel approach to path planning for multiple robots in bi-connected graphs [Text] / P. Surynek // 2009 IEEE international conference on robotics and automation. — IEEE. 2009. — P. 3613—3619.

79. Botea, A. Multi-agent path finding on strongly biconnected digraphs [Text] / A. Botea, P. Surynek // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 29. — 2015.

80. Yu, J. Average case constant factor time and distance optimal multi-robot path planning in well-connected environments [Text] / J. Yu // Autonomous Robots. — 2020. — Vol. 44, no. 3. — P. 469—483.

81. Standley, T. Finding optimal solutions to cooperative pathfinding problems [Text] / T. Standley // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 24. — 2010. — P. 173—178.

82. Enhanced partial expansion A [Text] / M. Goldenberg [et al.] // Journal of Artificial Intelligence Research. — 2014. — Vol. 50. — P. 141—187.

83. Wagner, G. Subdimensional expansion for multirobot path planning [Text] / G. Wagner, H. Choset // Artificial intelligence. — 2015. — Vol. 219. — P. 1—24.

84. Silver, D. Cooperative Pathfinding. [Text] / D. Silver // Aiide. — 2005. — Vol. 1. — P. 117—122.

85. Sturtevant, N. Improving collaborative pathfinding using map abstraction [Text] / N. Sturtevant, M. Buro // Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Vol. 2. — 2006. — P. 80—85.

86. Bnaya, Z. Conflict-oriented windowed hierarchical cooperative A [Text] / Z. Bnaya, A. Felner // 2014 ieee international conference on robotics and automation (icra). — IEEE. 2014. — P. 3743—3748.

87. Anytime multi-agent path finding via large neighborhood search [Text] / J. Li [et al.] // International Joint Conference on Artificial Intelligence 2021. — Association for the Advancement of Artificial Intelligence (AAAI). 2021. — P. 4127—4135.

88. Shaw, P. Using constraint programming and local search methods to solve vehicle routing problems [Text] / P. Shaw // International conference on principles and practice of constraint programming. — Springer. 1998. — P. 417—431.

89. Icbs: The improved conflict-based search algorithm for multi-agent pathfinding [Text] / E. Boyarski [et al.] // Proceedings of the International Symposium on Combinatorial Search. Vol. 6. — 2015. — P. 223—225.

90. Adding heuristics to conflict-based search for multi-agent path finding [Text] / A. Felner [et al.] // Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 28. — 2018. — P. 83—87.

91. Iterative-deepening conflict-based search [Text] / E. Boyarski [et al.] // International Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020. — Association for the Advancement of Artificial Intelligence (AAAI). 2020. — P. 4084—4090.

92. Andreychuk, A. Multi-agent path finding with kinematic constraints via conflict based search [Text] / A. Andreychuk // Russian Conference on Artificial Intelligence. — 2020. — P. 29—45.

93. Yu, J. Multi-agent path planning and network flow [Text] / J. Yu, S. M. LaValle // Algorithmic foundations of robotics X. — Springer, 2013. — P. 157—173.

94. Ford Jr, L. R. Flows in networks [Text]. Vol. 54 / L. R. Ford Jr, D. R. Fulkerson. — Princeton university press, 2015.

95. Conflict-based search with optimal task assignment [Text] / W. Honig [et al.] // Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. — 2018.

96. Okumura, K. Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution [Text] / K. Okumura, X. Defago // Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 32. — 2022. — P. 270—278.

97. Generalized target assignment and path finding using answer set programming [Text] / V. Nguyen [et al.] // Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017). — 2017. — P. 1216—1223.

98. Ma, H. Optimal Target Assignment and Path Finding for Teams of Agents [Text] / H. Ma, S. Koenig // Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016). — 2016. — P. 1144—1152.

99. Bartak, R. From classical to colored multi-agent path finding [Text] / R. Bartak, M. Ivanova, J. Svancara // Proceedings of the 14th International Symposium on Combinatorial Search (SoCS 2021). — 2021. — P. 150—152.

100. Lifelong multi-agent path finding in large-scale warehouses [Text] / J. Li [et al.] // Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021). — 2021. — P. 11272—11281.

101. Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks [Text] / H. Ma [et al.] // Proceedings of The 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2017). — International Foundation for Autonomous Agents, Multiagent Systems. 2017. — P. 837—845.

102. Integrated task assignment and path planning for capacitated multi-agent pickup and delivery [Text] / Z. Chen [et al.] // IEEE Robotics and Automation Letters. — 2021. — Vol. 6, no. 3. — P. 5816—5823.

103. Multi-Goal Multi-Agent Pickup and Delivery [Text] / Q. Xu [et al.] // Proceedings of the 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2022). — 2022.

104. Sturtevant, N. R. Benchmarks for grid-based pathfinding [Text] / N. R. Sturtevant // IEEE Transactions on Computational Intelligence and AI in Games. — 2012. — Vol. 4, no. 2. — P. 144—148.

105. Mueller, M. W. A computationally efficient motion primitive for quadrocopter trajectory generation [Text] / M. W. Mueller, M. Hehn, R. D'Andrea // IEEE transactions on robotics. — 2015. — Vol. 31, no. 6. — P. 1294—1310.

106. Searching with consistent prioritization for multi-agent path finding [Text] / H. Ma [et al.] // Proceedings of the AAAI conference on artificial intelligence. Vol. 33. — 2019. — P. 7643—7650.

107. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks [Text] / R. Stern [et al.] // Symposium on Combinatorial Search (SoCS). — 2019. — P. 151—158.

108. Ahuja, R. K. Network flows: theory, algorithms and applications [Text] / R. K. Ahuja, T. L. Magnanti, J. B. Orlin. — Prentice Hall, 1995.

109. Task and path planning for multi-agent pickup and delivery [Text] / M. Liu [et al.] // Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). — 2019.

110. Ford, L. R. Maximal flow through a network [Text] / L. R. Ford, D. R. Fulkerson // Canadian journal of Mathematics. — 1956. — Vol. 8. — P. 399—404.

111. Cruz-Mejia, O. A survey on exact algorithms for the maximum flow and minimum-cost flow problems [Text] / O. Cruz-Mejia, A. N. Letchford // Networks. — 2023.

112. Gonzalez, J. P. Using state dominance for path planning in dynamic environments with moving obstacles [Text] / J. P. Gonzalez, A. Dornbush, M. Likhachev // 2012 IEEE International Conference on Robotics and Automation. — IEEE. 2012. — P. 4009—4015.

113. Gross, O. The bottleneck assignment problem [Text] / O. Gross. — Rand, 1959.

114. Edmonds, J. Theoretical improvements in algorithmic efficiency for network flow problems [Text] / J. Edmonds, R. M. Karp // Journal of the ACM (JACM). — 1972. — Vol. 19, no. 2. — P. 248—264.

115. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks [Text] / R. Stern [et al.] // Symposium on Combinatorial Search. — 2019.

The author's publications

116. Ali, Z. Prioritized SIPP for Multi-agent Path Finding with Kinematic Constraints [Text] / Z. Ali, K. Yakovlev // Lecture Notes in Computer Science. — 2021. — Vol. 12998. — P. 1—13.

117. Ali, Z. A. Safe interval path planning with kinodynamic constraints [Text] / Z. A. Ali, K. Yakovlev // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. — 2023. — P. 12330—12337.

118. Ali, Z. A. Improved Anonymous Multi-Agent Path Finding Algorithm [Text] / Z. A. Ali, K. Yakovlev // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. — 2024. — P. 17291—17298.