Интервальные временные ограничения для планирования согласованных движений многозвенных манипуляторов
Ключевые слова:
планирование движения, планирование траекторий, многоагентное планирование, манипулятор, конфликтно-ориентированное планирование, поиск на основе конфликтов, поиск по графу, интервальные ограничения, временные ограниченияАннотация
В работе рассматривается задача планирования согласованных движений для системы многозвенных роботов-манипуляторов. Одним из перспективных современных подходов к её решению является конфликтно-ориентированное планирование, позволяющее отказаться от построения комбинированного пространства поиска высокой размерности за счет перехода к последовательному решению совокупности задач более низкой размерности. Этот переход осуществляется путем задания пространственно-временных ограничений при наличии конфликта в индивидуальных планах манипуляторов и последующего пере-планирования с учетом наложенных ограничений. К сожалению, известные к настоящему моменту способы наложения ограничений оперируют отдельными моментами времени, что снижает их эффективность на практике. В данной работе представляется новый алгоритм конфликтно-ориентированного планирования, основанный не на точечных, а на интервальных временных ограничениях – GECBS-T. С теоретической точки зрения, предлагаемый алгоритм гарантирует ограниченную суб-оптимальность конструируемых решений, т.е. при любом наперёд заданном пользователем ограничении w > 1, стоимость решения GECBS-T не будет превышать стоимость оптимального решения более, чем в w раз. На практике же, предлагаемый алгоритм существенно превосходит аналогичные алгоритмы по скорости решения задач планирования, что подтверждается проведенными экспериментами в робототехническом симуляторе mujoco, включающими 2-4 робота-манипулятора Kuka с 7 степенями свободы каждый.
Литература
2. Shaoul Y., Veerapaneni R., Likhachev M., Li J. Unconstraining multi-robot manipulation: Enabling arbitrary constraints in ecbs with bounded sub-optimality. Proceedings of the International Symposium on Combinatorial Search. 2024. vol. 17. pp. 109–117.
3. Ma H., Koenig S. Ai buzzwords explained: multi-agent path finding (mapf). AI Matters. 2017. vol. 3(3). pp. 15–19.
4. Stern R., Sturtevant N., Felner A., Koenig S., Ma H., Walker T., Li J., Atzmon D., Cohen L., Kumar T.K., et al. Multi-agent pathfinding: Definitions, variants, and benchmarks. Proceedings of the International Symposium on Combinatorial Search. 2019. vol. 10. pp. 151–158.
5. Ma H., Harabor D., Stuckey P.J., Li J., Koenig S. Searching with consistent prioritization for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence. 2019. vol. 33. pp. 7643–7650.
6. Chan S.-H., Stern R., Felner A., Koenig S. Greedy priority-based search for suboptimal multi-agent path finding. Proceedings of the International Symposium on Combinatorial Search. 2023. vol. 16. pp. 11–19.
7. Zhang S., Li J., Huang T., Koenig S., Dilkina B. Learning a priority ordering for prioritized planning in multi-agent path finding. Proceedings of the International Symposium on Combinatorial Search. 2022. vol. 15. pp. 208–216.
8. Sharon G., Stern R., Felner A., Sturtevant N.R. Conflict-based search for optimal multi-agent pathfinding. Artificial intelligence. 2015. vol. 219. pp. 40–66.
9. Shaoul Y., Mishani I., Likhachev M., Li J. Accelerating search-based planning for multi-robot manipulation by leveraging online-generated experiences. Proceedings of the International Conference on Automated Planning and Scheduling. 2024. vol. 34. pp. 523–531.
10. Chen J., Li J., Huang Y., Garrett C., Sun D., Fan C., Hofmann A., Mueller C., Koenig S., Williams B.C. Cooperative task and motion planning for multi-arm assembly systems. arXiv preprint arXiv:2203.02475. 2022.
11. LaValle S. Rapidly-exploring random trees: A new tool for path planning. Research Report 9811. 1998.
12. Kuffner J.J., LaValle S.M. Rrt-connect: An efficient approach to single-query path planning. Proceedings 2000 ICRA. Millennium conference. IEEE international conference on robotics and automation. Symposia proceedings (Cat. No. 00CH37065). IEEE, 2000. vol. 2. pp. 995–1001.
13. Lacevic B., Osmankovic D.. Improved c-space exploration and path planning for robotic manipulators using distance information. 2020 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2020. pp. 1176–1182.
14. Karaman S., Frazzoli E. Sampling-based algorithms for optimal motion planning. The international journal of robotics research. 2011. vol. 30(7). pp. 846–894.
15. Zhang D., Zhu G., Zhang Q. Multi-robot motion planning: A learning-based artificial potential field solution. 2nd Conference on Fully Actuated System Theory and Applications (CFASTA). IEEE, 2023. pp. 233–238.
16. Shaoul Y., Mishani I., Vats S., Li J., Likhachev M. Multi-robot motion planning with diffusion models. arXiv preprint arXiv:2410.03072. 2024.
17. Aljalbout E., Karl M., van der Smagt P. Clas: Coordinating multi-robot manipulation with central latent action spaces. Learning for Dynamics and Control Conference. PMLR, 2023. pp. 1152–1166.
18. Sharon G., Stern R., Felner A., Sturtevant N.R. Conflict-based search for optimal multi-agent pathfinding. Artificial intelligence. 2015. vol. 219. pp. 40–66.
19. Ebendt R., Drechsler R. Weighted a search–unifying view and application. Artificial Intelligence. 2009. vol. 173(14). pp. 1310–1342.
20. Li J., Ruml W., Koenig S. Eecbs: A bounded-suboptimal search for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence. 2021. vol. 35(14). pp. 12353–12362.
Time Range Constraints for Motion Planning for Manipulators
Abstract
This paper addresses the problem of coordinated motion planning for multi-link robotic manipulator systems. One of the promising modern approaches to solving this problem is conflict-based planning, which avoids constructing a high-dimensional joint search space by sequentially solving a series of lower-dimensional problems. This is achieved by introducing spatio-temporal constraints whenever conflicts arise in individual manipulator plans, followed by replanning with these constraints in place. Unfortunately, existing methods that use constraints operate with individual time points, which reduces their practical efficiency. In this work, we present a novel conflict-based planning algorithm that utilizes interval-based temporal constraints rather than point-based ones – GECBS-T. Theoretically, the proposed algorithm guarantees bounded sub-optimality of the generated solutions; that is, for any user-defined bound w > 1, the cost of the GECBS-T solution will not exceed w times the cost of the optimal solution. In practice, the proposed algorithm significantly outperforms analogous algorithms in terms of planning speed, as confirmed by experiments conducted in the MuJoCo robotics simulator involving 2–4 KUKA robotic manipulators, each with 7 degrees of freedom.
Опубликован
Как цитировать
Раздел
Copyright (c) Андрей Сергеевич Зайцев, Константин Сергеевич Яковлев
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).