ISSN 2071-8594

Russian academy of sciences

Editor-in-Chief

Gennady Osipov

A.A. Andreychuk Algorithm for planning and coordination of a set of trajectories for a group of intelligent agents

Abstract.

The paper considers the problem of planning a set of non-conflicting trajectories for a group of intelligent agents. The proposed algorithm uses a prioritized approach and works in two stages: independent planning of individual trajectories of agents; trajectories’ coordination. A new method for trajectories’ coordination is proposed that works by adding time delays only. Due to the representation of the time axis in the form of a sequence of intervals, rather than discrete moments of time, the algorithm is able to coordinate trajectories constructed any-angle path-planning algorithms. The carried out model experimental studies have confirmed the applicability of the proposed algorithm, its high computational efficiency and the comparable quality of the solutions sought.

Keywords:

path-planning, multi-agent systems, conflict resolving, A*, Theta*, grid.

PP. 72-85.

DOI 10.14357/20718594180407

References

1. Makarov, D.A., Panov, A.I., Yakovlev, K.S. 2015. Аrkhitektura mnogourovnevoj intellektual'noj sistemy upravleniya bespilotnymi letatel'nymi apparatami [The architecture of a multi-level intelligent control system for unmanned aerial vehicles] //Iskusstvennyj intellekt i prinyatie reshenij [Artificial Intelligence and Decision Taking]. 3:18–32.
2. Bukhvalov, O.L., Gorodetskij, V.I., Karasev, O.V. et al. 2012. Proizvodstvennaya logistika: Strategicheskoe planirovanie, prognozirovanie i upravlenie konfliktami [Industrial Logistics: Strategic Planning, Forecasting and Conflict Management] //Izvestiya YUFU [SFU Tidings]. 3:209–218.
3. Ivanov, A.M. 2013. Razrabotka sistemy mezhob"ektnogo vzaimodejstviya intellektual'nykh transportnykh sredstv [Development of a system of interobject interaction of intelligent vehicles] // Izvestiya VolgGTU. Seriya «Nazemnye transportnye sistemy» [ VolgSTU Tidings. Series "Land transport systems."] Vol. 7, 21(124):74–77.
4. Ronzhin, A.L., Vu, D.K., Nguen, V.V., Solenaya, O.Ya. 2017. Kontseptual'naya i algoritmicheskie modeli sovmestnogo funktsionirovaniya robotizirovannoj platformy i nabora BLА pri vypolnenii agrarnykh operatsij [Conceptual and algorithmic models of the joint operation of a robotic platform and a set of UAVs in the performance of agrarian operations] // IV vserossijskij nauchno-prakticheskij seminar "Bespilotnye transportnye sredstva s ehlementami iskusstvennogo intellekta". Trudy seminara. Kazan'. [IV All-Russian Scientific and Practical Seminar "Unmanned Vehicles with Artificial Intelligence Elements". Proceedings of the seminar. Kazan]. 183 -192.
5. Motienko, А.I. 2016. Planirovanie takticheskoj traektorii dvizheniya avtomatizirovannykh robototekhnicheskikh sredstv pri likvidatsii posledstvij chrezvychajnykh situatsij [Planning of the tactical trajectory of the movement of automated robotic means during the liquidation of the consequences of emergency situations] // Nauchnye vedomosti Belgorodskogo gosudarstvennogo universiteta. Seriya: EHkonomika. Informatika. [Scientific bulletins of the Belgorod State University. Series: The Economy. Computer science.]. Vol. 37, 2(223):139–143.
6. Van Den Berg, J., Guy, S., Lin, M., Manocha, D. 2011. Reciprocal n-body collision avoidance //Robotics research. – Springer, Berlin, Heidelberg. 3–19.
7. Hart, P. E., Nilsson, N. J., Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths //IEEE transactions on Systems Science and Cybernetics. Vol. 4, 2:100–107.
8. Daniel, K., Nash, A., Koenig, S., Felner, A. 2010. Theta*: Any-angle path planning on grids //Journal of Artificial Intelligence Research. Vol. 39:533–579.
9. Аndreychuk, А.А., Yakovlev, K.S. 2017. Metody planirovaniya traektorii na ploskosti s uchetom geometricheskikh ogranichenij [Methods for planning a trajectory on a plane with geometric constraints] // Izvestiya RАN. Teoriya i sistemy upravleniya. [Tidings of RAS. Theory and control systems]. 6:125–140.
10. Standley, T.S. 2010. Finding Optimal Solutions to Cooperative Pathfinding Problems //Proceedings of The 24th AAAI Conference on Artificial Intelligence (AAAI2010). Vol. 1:28–29.
11. Sharon, G., Stern, R., Felner, A., Sturtevant, N.R. 2015. Conflict-based search for optimal multi-agent pathfinding //Artificial Intelligence. Vol. 219:40–66.
12. Wagner, G., Choset, H. 2011. M*: A complete multirobot path planning algorithm with performance bounds //Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on. – IEEE. 3260–3267.
13. Аndreychuk, А.А., Yakovlev, K.S. 2016. Metod razresheniya konfliktov pri planirovanii prostranstvennykh traektorij dlya gruppy bespilotnykh letatel'nykh apparatov [Method of conflict resolution in the planning of spatial trajectories for a group of unmanned aerial vehicles] //Tretij Vserossijskij nauchno-prakticheskij seminar «Bespilotnye transportnye sredstva s ehlementami iskusstvennogo intellekta» (BTS-II-2016, 22-23 sentyabrya 2016 g., g. Innopolis, Respublika Tatarstan, Rossiya): Trudy seminara. – M: Izd-vo «Pero», [The Third All-Russian Scientific and Practical Seminar "Unmanned Vehicles with Artificial Intelligence Elements" (BPS-AI-2016, September 22-23, 2016, Innopolis, Republic of Tatarstan , Russia): Proceedings of the Seminar. - M: Publishing house "Pero"]. 31–40.
14. Silver, D. 2005. Cooperative Pathfinding //AIIDE. Vol. 1:117–122.
15. Wang, K. H. C., Botea, A. 2011. MAPP: a scalable multi-agent path planning algorithm with tractability and completeness guarantees //Journal of Artificial Intelligence Research. Vol. 42:55-90.
16. Erdmann, M., Lozano-Perez, T. 1987. On multiple moving objects //Algorithmica. Vol. 2:1419–1424
17. Cˇap, M., Nov´ak, P., Kleiner, A., Seleck´y, M. 2015. Prioritized planning algorithms for trajectory coordination of multiple mobile robots. //IEEE Transactions on Automation Science and Engineering, Vol. 12(3):835–849
18. Harabor, D., Grastien A., Oz D., Aksakalli V. 2016. Optimal any-angle pathfinding in practice. //Journal of Artificial Intelligence Research. 56:89–118
19. Yakovlev, K., Andreychuk, A. 2017. Any-angle pathfinding for multiple agents based on sipp algorithm. //Proceedings of The 27th International Conference on Automated Planning and Scheduling (ICAPS2017). 586–593
20. Phillips, M., Likhachev, M. 2011. SIPP: Safe interval path planning for dynamic environments. //Proceedings of The 2011 IEEE International Conference on Robotics and Automation (ICRA-2011). 5628–5635.
21. Yap, P. 2002. Grid-based path-finding //In Proceedings of 15th Conference of the Canadian Society for Computational Studies of Intelligence, Springer: Berlin, Heidelberg. 44-55.
22. Guy, S.J., Karamouzas, I. 2015. Guide to anticipatory collision avoidance. //Game AI Pro 2: Collected Wisdom of Game AI Professionals, S. Rabin, Ed., ch. 19:195–208.