?
Applying MAPP Algorithm for Cooperative Path Finding in Urban Environments
P. 1-10.
Andreychuk A., Yakovlev K.
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 of the experimental studies provide an opportunity to claim that MAPP is a highly efficient planner for solving considered types of tasks.
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., 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., , 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., 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
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., Atzmon D. et al., , in : Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019). : International Joint Conferences on Artificial Intelligence, 2019. 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 ...
Added: August 21, 2019
Yakovlev K., Baskin E., Hramolin I., , in : Artificial Intelligence: Methodology, Systems, and Applications 16th International Conference, AIMSA 2014, Varna, Bulgaria, September 11-13, 2014. Proceedings. Vol. 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
Soboleva Natalia, Yakovlev K., , in : Proceedings of the 42nd German Conference on Artificial Intelligence (KI 2019), Kassel, Germany, September 23-26, 2019. : Springer, 2019. P. 316-324.
2D path planning in static environment is a well-known problem and one of the common ways to solve it is to (1) represent the environment as a grid and (2) perform a heuristic search for a path on it. At the same time 2D grid resembles much a digital image, thus an appealing idea comes ...
Added: February 3, 2020
Panov A. I., Yakovlev K., , in : Robot Intelligence Technology and Applications 4. : Springer, 2016. P. 3-20.
In this paper we outline the approach of solving special type of navigation tasks for robotic systems, when a coalition of robots (agents) acts in the 2D environment, which can be modified by the actions, and share the same goal location. The latter is originally unreachable for some members of the coalition, but the common ...
Added: August 4, 2016
Dergachev S., Yakovlev K., Муравьев К. Ф., , in : IFAC-PapersOnLine. Vol. 55. Issue 38: 13th IFAC Symposium on Robot Control SYROCO 2022.: Elsevier, 2022. P. 80-85.
Safe navigation in uneven terrains is an important problem in robotic research. In this paper we propose a 2.5D navigation system which consists of elevation map building, path planning and local path following with obstacle avoidance. For local path following we use Model Predictive Path Integral (MPPI) control method. We propose novel cost-functions for MPPI ...
Added: September 8, 2023
Лавренов Р. О., Magid E., Мацуно Ф. et al., Информатика и автоматизация (Труды СПИИРАН) 2019 Т. 18 № 1 С. 57-84
Path planning for autonomous mobile robots is an important task within robotics field. It is common to use one of the two classical approaches in path planning: a global approach when an entire map of a working environment is available for a robot or local methods, which require the robot to detect obstacles with a ...
Added: November 9, 2021
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
Makarov I., Peter Zyuzin, Pavel Polyakov et al., , in : Proceedings of the Third Workshop on Experimental Economics and Machine Learning (EEML 2016), Moscow, Russia, July 18, 2016. Vol. 1627.: Aachen : CEUR Workshop Proceedings, 2016. Ch. 3. P. 24-33.
We present two examples of how human-like behavior can be implemented in a model of computer player to improve its characteristics and decision-making patterns in video game. At first, we describe a reinforcement learning model, which helps to choose the best weapon depending on reward values obtained from shooting combat situations. Secondly, we consider an ...
Added: August 27, 2016
Panov A. I., Yakovlev K., Suvorov R. E., Procedia Computer Science 2018 Vol. 123 P. 347-353
Single-shot grid-based path finding is an important problem with the applications in robotics, video games etc. Typically in AI community heuristic search methods (based on A And its variations) are used to solve it. In this work we present the results of preliminary studies on how neural networks can be utilized to path planning on ...
Added: September 3, 2018
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
Makarov I., Pavel Polyakov, Roman Karpichev, , in : Supplementary Proceedings of the 7th International Conference on Analysis of Images, Social Networks and Texts (AIST-SUP 2018), Moscow, Russia, July 5-7, 2018. : Aachen : CEUR Workshop Proceedings, 2018. P. 129-140.
We present an obstacle avoiding path planning method based on a Voronoi diagram adjusted with tactical component in a first-person shooter video game. We use a visibility measure to aggregate information on cover positions in offline and online game modes. In order to incorporate online learning based on frag map, we introduce a path finding ...
Added: September 5, 2018
Andreychuk A., Yakovlev K., , in : Interactive Collaborative Robotics: Third International Conference, ICR 2018, Leipzig, Germany, September 18–22, 2018, Proceedings. : Springer, 2018. P. 13-22.
The problem of planning a set of paths for the coalition of robots (agents) with different capabilities is considered in the paper. Some agents can modify the environment by destructing the obstacles thus allowing the other ones to shorten their paths to the goal. As a result the mutual solution of lower cost, e.g. time ...
Added: August 13, 2019
Mavrin I., Tsoy T., Magid E., , in : 2022 13th Asian Control Conference (ASCC). : IEEE, 2022. P. 1413-1418.
An efficient autonomous exploration of an unknown environment is an important task for mobile robots, which is required in many domains. This paper considers three existing exploration approaches: frontier exploration algorithm (FEA), greedy algorithm (GrA) and Ergodic Environmental Exploration algorithm (E3). While original E3 deals only with empty environments, we propose a new modified version ...
Added: October 28, 2022
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, Part 1. * 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
Laurent F., Schneider M., Scheller C. et al., , in : Proceedings of Machine Learning Research. Vol. 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
Emel’yanov S., Makarov D., Panov A. I. et al., Cognitive Systems Research 2016 Vol. 39 P. 58-72
Extensive use of unmanned aerial vehicles (UAVs) in recent years has induced the rapid growth of research areas related to UAV production. Among these, the design of control systems capable of automating a wide range of UAV activities is one of the most actively explored and evolving. Currently, researchers and developers are interested in designing ...
Added: February 9, 2016
Natalia Soboleva, Konstantin Yakovlev, , in : Proceedings 16th Russian Conference on Artificial Intelligence (RCAI 2018). Issue 934.: Cham : Springer, 2018. P. 206-217.
Problem of finding 2D paths of special shape, e.g. paths comprised of line segments having the property that the angle between any two consecutive segments does not exceed the predefined threshold, is considered in the paper. This problem is harder to solve than the one when shortest paths of any shape are sought, since the ...
Added: August 14, 2019
Andreychuk A., Yakovlev K., Boyarski E. et al., , in : The Thirty-Fifth AAAI Conference on Artificial Intelligence. Technical Tracks 13. Vol. 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
Safin R., Lavrenov R., Tsoy T. et al., , in : Interactive Collaborative Robotics: 6th International Conference, ICR 2021, St. Petersburg, Russia, September 27–30, 2021, Proceedings. : Springer, 2021. Ch. 16. P. 182-193.
This paper describes a design and an implementation of a small-scale robotic transportation system, which operates in a smart hospital environment. Within a proposed framework unmanned ground vehicles (UGV) perform transportation tasks between multiple stations that are located in different rooms. The UGVs navigate in the environment with moving objects in accordance with basic traffic ...
Added: October 21, 2021