?
Multi-Agent Pathfinding with Continuous Time
P. 39–45.
Multi-Agent Pathfinding (MAPF) is the problem offinding paths for multiple agents such that everyagent reaches its goal and the agents do not col-lide. Most prior work on MAPF was on grids, as-sumed agents’ actions have uniform duration, andthat time is discretized into timesteps. We proposea MAPF algorithm that does not rely on these as-sumptions, is complete, and provides provably op-timal solutions. This algorithm is based on a noveladaptation of Safe interval path planning (SIPP), acontinuous time single-agent planning algorithm,and a modified version of Conflict-based search(CBS), a state of the art multi-agent pathfinding al-gorithm. We analyze this algorithm, discuss its prosand cons, and evaluate it experimentally on severalstandard benchmarks.
In book
International Joint Conferences on Artificial Intelligence, 2019.
Dergachev S., Yakovlev K., , in: ECAI 2024. 27th European Conference on Artificial Intelligence, October 19 – 24 October 2024, Santiago de Compostela, Spain – Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024).: IOS Press, 2024. P. 4344–4351.
Added: September 11, 2024
Dergachev S., Yakovlev K., , in: Interactive Collaborative Robotics. 9th International Conference, ICR 2024, Mexico City, Mexico, October 14–18, 2024, Proceedings.: Cham: Springer, 2024. P. 186–200.
Added: September 11, 2024
Dergachev S., Yakovlev K., , in: Advances in Computational Intelligence. 21st Mexican International Conference on Artificial Intelligence, MICAI 2022, Monterrey, Mexico, October 24–29, 2022, Proceedings* 1.: Cham: Springer, 2022. P. 355–367.
Multi-agent pathfinding (MAPF) is a challenging problem which is hard to solve optimally even when simplifying assumptions are adopted, e.g. planar graphs (typically – grids), discretized time, uniform duration of move and wait actions etc. On the other hand, MAPF under such restrictive assumptions (also known as the Classical MAPF) is equivalent to the so-called ...
Added: May 16, 2023
Andreychuk A., Yakovlev K., Surynek P. et al., Artificial Intelligence 2022 Vol. 305 Article 103662
Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that each agent reaches its goal and the agents do not collide. In recent years, variants of MAPF have risen in a wide range of real-world applications such as warehouse management and autonomous vehicles. Optimizing common MAPF objectives, such as minimizing sum-of-costs ...
Added: August 26, 2022
Andreychuk A., Yakovlev K., Boyarski E. et al., , in: The Thirty-Fifth AAAI Conference on Artificial Intelligence. Technical Tracks 13Vol. 35.: AAAI Press, 2021. P. 11220–11227.
Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does ...
Added: October 21, 2021
Laurent F., Schneider M., Scheller C. et al., , in: Proceedings of Machine Learning ResearchVol. 133: Proceedings of the NeurIPS 2020: Competition and Demonstration Track.: PMLR, 2021. P. 275–301.
The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP). The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur, for example the breakdown of a vehicle. While solving the VRSP in various settings has been an active area in operations research ...
Added: September 6, 2021
Yakovlev K., Andreychuk A., Stern R., , in: Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020).: AAAI Press, 2020. P. 300–304.
Added: October 21, 2020
Yakovlev K., Andreychuk A., Vorobyev V., , in: Proceedings of the 2019 European Conference on Mobile Robotics (ECMR 2019).: Prague: IEEE, 2019. P. 1–6.
Methods for centralized planning of the collision-free trajectories for a fleet of mobile robots typically solve the discretized version of the problem and rely on numerous simplifying assumptions, e.g. moves of uniform duration, cardinal only translations, equal speed and size of the robots etc., thus the resultant plans can not always be directly executed by ...
Added: January 15, 2020
Andreychuk A., Yakovlev K., , in: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018).: IFAAMAS, 2018. P. 2177–2179.
We introduce and empirically evaluate two techniques aimed at enhancing the performance of multi-robot prioritized path planning.The first technique is the deterministic procedure for re-scheduling(as opposed to well-known approach based on random restarts), the second one is the heuristic procedure that modifies the search-spaceof the individual planner involved in the prioritized path findin ...
Added: August 14, 2019
Andreychuk A., Yakovlev K., , in: Interactive Collaborative Robotics: Second International Conference, ICR 2017, Hatfield, UK, September 12-16, 2017, Proceedings.: Springer, 2017. P. 1–10.
The paper considers the problem of planning a set of non-conflict trajectories for the coalition of intelligent agents (mobile robots). Two divergent approaches, e.g. centralized and decentralized, are surveyed and analyzed. Decentralized planner – MAPP is described and applied to the task of finding trajectories for dozens UAVs performing nap-of-the-earth flight in urban environments. Results ...
Added: November 6, 2017
Yakovlev K., Makarov D., Scientific and Technical Information Processing 2015 Vol. 42 No. 5 P. 347–358
In the article we solve path planning task for an agent being multirotor unmanned aerial vehicle (multicopter). We propose an approach of estimating path geometry constraints based on UAV flight dynamics model and control constraints. Than we introduce a new path finding method which takes into consideration those geometry constraints and study this method both ...
Added: July 17, 2017
Yakovlev K., Andreychuk A., , in: Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS 2017).: Palo Alto: AAAI Press, 2017. P. 586–593.
The problem of finding conflict-free trajectories for multiple agents of identical circular shape, operating in shared 2D workspace, is addressed in the paper and decoupled, e.g., prioritized, approach is used to solve this problem. Agents’ workspace is tessellated into the square grid on which any-angle moves are allowed, e.g. each agent can move into an ...
Added: July 17, 2017
Yakovlev K., Baskin E., Hramoin I., , in: Proceedings of the 38th Annual German Conference on Artificial Intelligence (KI 2015), Dresden, Germany, September 21-25, 2015.: Switzerland: Springer, 2015. P. 208–221.
Square grids are commonly used in robotics and game development as spatial models and well known in AI community heuristic search algorithms (such as A*, JPS, Theta* etc.) are widely used for path planning on grids. A lot of research is concentrated on finding the shortest (in geometrical sense) paths while in many applications finding ...
Added: July 14, 2017
Yakovlev K., Baskin E., Hramolin I., , in: Artificial Intelligence: Methodology, Systems, and Applications 16th International Conference, AIMSA 2014, Varna, Bulgaria, September 11-13, 2014. ProceedingsVol. 8722.: Dordrecht, L., Cham, Heidelberg, NY: Springer, 2014. P. 278–285.
Path planning is typically considered in Artificial Intelligence as a graph searching problem and R* is state-of-the-art algorithm tailored to solve it. The algorithm decomposes given path finding task into the series of subtasks each of which can be easily (in computational sense) solved by well-known methods (such as A*). Parameterized random choice is used ...
Added: April 24, 2015