Объектно-ориентированная среда для разработки приложений планирования движения
https://doi.org/10.15514/ISPRAS-2017-29(5)-11
Аннотация
Обсуждаются принципы организации и функционирования инструментальной среды для программной реализации моделей, методов и приложений теории планирования движения. Среда предоставляет развитый набор готовых к использованию программных компонентов для автоматического построения бесконфликтных траекторий для робота, перемещаемого в статическом и динамическом трехмерном окружении. Организация среды в виде объектно-ориентированного каркаса обеспечивает развитие, адаптацию и гибкое конфигурирование разработанных программных компонентов в составе целевых приложений. Благодаря выделенным интерфейсам разного уровня и предусмотренным точкам расширения среда допускает интеграцию со сторонними прикладными системами.
Об авторах
К. А. Казаков
Институт системного программирования им. В.П. Иванникова РАН
Россия
Россия
В. А. Семенов
Институт системного программирования им. В.П. Иванникова РАН; Московский физико-технический институт
Россия
Россия
Список литературы
1. LaValle S.M. Planning Algorithms. Cambridge University Press, 2006.
2. Казаков К.А., Семенов В.А. Обзор современных методов планирования движения. Труды ИСП РАН том 28, 2016, выпуск 4. стр. 241–292. 10.15514/ISPRAS-2016-28(4)-14
3. Semenov V.A., Kazakov K.A., Zolotov V.A. Global path planning in 4D environments using topological mapping. eWork Ebus. Archit. Eng. Constr. 2012. pp. 263–269.
4. Semenov V.A., Kazakov K.A., Zolotov V.A. Advanced spatio-temporal validation of construction schedules. ICCCBE. 2012.
5. Dubins L.E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. 1957.
6. Reeds J.A., Shepp L.A. Optimal paths for a car that goes both forwards and backwards. Pacific J. Math. 1990. Vol. 145, № 2. pp. 367–393.
7. Chitsaz H., LaValle S.M., Balkcom D.J., Mason M.T. Minimum wheel-rotation paths for differential-drive mobile robots. Proc. - IEEE Int. Conf. Robot. Autom. 2006. Vol. 2006, № May. pp. 1616–1623.
8. Koenig S., Likhachev M. Fast Replanning for Navigation in Unknown Terrain Technology. 2002. Vol. XX, № May. pp. 968–975.
9. Naderi K., Rajamaki J., Hamalainen P. RT-RRT*: A Real-Time Path Planning Algorithm Based On RRT*. Proc. 8th ACM SIGGRAPH Conf. Motion Games - SA ’15. 2015. pp. 113–118.
10. Gipson I., Gupta K., Greenspan M. MPK: An open extensible motion planning kernel. J. Robot. Syst. 2001. Vol. 18, № 8. pp. 433–443.
11. Diankov R. Automated Construction of Robotic Manipulation Programs Architecture. 2010. Vol. Ph.D. pp. 1–263.
12. Sucan I., Moll M., Kavraki L.E. The Open Motion Planning Library IEEE Robot. Autom. Mag. 2012. Vol. 19, № 4. pp. 72–82.
13. Казаков К.А., Морозов С.В., Семенов В.А., Тарлапан О.А. Применение топологических схем для глобального планирования движения в сложном динамическом окружении. ITSE, 2016.
14. Semenov V.A. et al. Global path planning in complex environments using metric and topological schemes. Proc. CIB W78-W102. 2011. pp. 26–28.
15. Mamou K., Ghorbel F. A simple and efficient approach for 3D mesh approximate convex decomposition. 16th IEEE Int. Conf. Image Process. 2009. pp. 3501–3504.
16. Золотов В.А., Семенов В.А. Перспективные схемы пространственно-временной индексации для визуального моделирования масштабных индустриальных проектов. Труды ИСП РАН том 26, вып. 2, стр. 175–196. 10.15514/ISPRAS-2014-26(2)-8
17. Bergen G. Van Den. Efficient Collision Detection of Complex Deformable Models using AABB Trees. J. Graph. Tools. 1997. Vol. 2. pp. 1–13.
18. Gottschalk S., Lin M.C., Manocha D. OBB Tree: A Hierarchical Structure for Rapid Interference Detection. Proc. SIGGRAPH 96. 1996. № 8920219. pp. 171–180.
19. Li H., Wu Y., Wiu Y. An improved dynamic-octree-based judging method of real-time node in moving geometry. Proceedings of the 2013 International Conference on Intelligent Control and Information Processing, ICICIP 2013. 2013. pp. 333–337.
20. Tracy D.J., Buss S.R., Woods B.M. Efficient large-scale sweep and prune methods with AABB insertion and removal. Proc. - IEEE Virtual Real. 2009. pp. 191–198.
21. van den Bergen G. Proximity queries and penetration depth computation on 3d game objects. Game Dev. Conf. 2001.
22. Gilbert E.G., Johnson D.W., S.S. K. A Fast Procedure for Computing Distance Between Complex Objects in Three-Dimensional Space. 1988.
23. Russell S.J., Norvig P. Artificial Intelligence: A Modern Approach. Neurocomputing. 1995. Vol. 9, pp. 215-218.
24. Karaman S., Frazzoli E. Sampling-based algorithms for optimal motion planning. Int. J. Robot., vol. 30, № 7, 2011, pp. 846–894.
25. Kuffner J.J., LaValle S.M. RRT-connect: An efficient approach to single-query path planning. Proc. IEEE Int. Conf. Robot. Autom. ICRA ’00. 2000. Vol. 2, № Icra. pp. 995--1001 vol.2.
26. Jaillet L., Yershova A. Lavalle S.M. Simeon T. Adaptive tuning of the sampling domain for dynamic-domain RRTs. 2005 IEEE/RSJ Int. Conf. Intell. Robot. Syst. IROS. 2005. pp. 4086–4091.
27. Ferre E., Laumond J.-P. An iterative diffusion algorithm for part disassembly. IEEE Int. Conf. Robot. Autom. 2004. Proceedings. ICRA ’04. 2004. Vol.3, pp. 3149–3154.
28. Geraerts R., Overmars M.H. Creating High-quality Paths for Motion Planning. Int. J. Rob. Res. 2007. Vol. 26, № 8. P. 845–863.
29. Jaillet L., Cortes J., Simeon T. Sampling-Based Path Planning on Costmaps Configuration-space. IEEE Trans. Robot. 2010. Vol. 26, № 4. P. 635–646.
30. Koenig S., Likhachev M., Furcy D. Lifelong Planning A*. Artif. Intell. 2004. Vol. 155, № 1–2. pp. 93–146.
31. Koenig S., Likhachev M. D* Lite. Proc. Eighteenth Natl. Conf. Artif. Intell. 2002. pp. 476–483.
32. Kuffner J.J. Effective sampling and distance metrics for 3D rigid body path planning. Proc. - IEEE Int. Conf. Robot. Autom. 2004. Vol. 4, pp. 3993--3998.
33. Amato N.M., Bayazit O.B., Dale L.K., Jones C., Vallejo D. OBPRM: An Obstacle-Based PRM for 3D Workspaces. Proc. Third Work. Algorithmic Found. Robot. Algorithmic Perspect. Algorithmic Perspect. 1998. pp. 155–168.
34. Yeh H.Y., Thomas S., Eppstein D., Amato N.M. UOBPRM: A uniformly distributed obstacle-based PRM. IEEE Int. Conf. Intell. Robot. Syst. 2012. pp. 2655–2662.
35. Hsu D., Jiang T., Reif J., Sun Z. The bridge test for sampling narrow passages with probabilistic roadmap planners. IEEE Int. Conf. Robot. Autom. 2003. Proceedings. ICRA ’03. 2003. Vol. 3. pp. 4420–4426.
36. Nissoux C., Simeon T., Laumond J.-P. Visibility based probabilistic roadmaps. 1999 IEEE/RSJ Int. Conf. Intell. Robot. Syst. 1999. IROS ’99. Proc. 1999. Vol. 3. pp. 1316–1321 vol.3.
37. Lien J.-M., Thomas S., Amato N.M. A general framework for sampling on the medial axis of the free space 2003 IEEE Int. Conf. Robot. Autom. (Cat. No.03CH37422). 2003. Vol. 3. pp. 4439–4444.
38. Berenson D., Srinivasa S., Ferguson D., Kuffner J.J. Manipulation Planning on Constraint Manifolds. Robotics and Automation, 2009. ICRA’09. 2009.
39. Berenson D., Srinivasa S., Kuffner J.J. Task Space Regions: A framework for pose-constrained manipulation planning. Int. J. Rob. Res. 2011. Vol. 30, № 12. pp. 1435–1460.
40. Redon S., Kheddar A., Coquillart S. Fast continuous collision detection between rigid bodies. Comput. Graph. Forum. 2002. Vol. 21, № 3. pp. 279–287.
41. Redon S., Lin M.C., Manocha D., Kim Y.J. Fast Continuous Collision Detection for Articulated Models. J. Comput. Inf. Sci. Eng. 2005. Vol. 5, № 2. pp. 126.
42. Devaurs D., Simeon T., Cortes J. Optimal Path Planning in Complex Cost Spaces with Sampling-Based Algorithms. IEEE Trans. Autom. Sci. Eng. 2016. Vol. 13, № 2. pp. 415–424.
43. Yershova A., LaValle S.M. Improving Motion Planning Alorithms by Efficient Nearest-Neighbor Searching. IEEE Trans. Robot. 2006. pp. 1–8.
44. Gipson B., Moll M., Kavraki L.E. Resolution Independent Density Estimation for motion planning in high-dimensional spaces. Proc. IEEE Int. Conf. Robot. Autom. 2013. pp. 2437–2443.
45. Fredriksson K. Geometric Near-neighbor Access Tree (GNAT) revisited. 2016.
46. Yianilos P.N. Data structures and algorithms for nearest neighbor search in general metric spaces. Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. 1993. pp. 311–321.
47. Sanchez G., Latombe J.C. A single-query bi-directional probabilistic roadmap planner with lazy collision checking Robotics Research. 2003. pp. 403–417.
48. Kavraki L.E., Svestka P., Latombe J.C., Overmars M.H. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 1996. Vol. 12, № 4. pp. 566–580.
49. Kazakov K.A., Semenov V.A., Zolotov V.A. Topological Mapping Complex 3D Environments Using Occupancy Octrees. 21st Int. Conf. Comput. Graph. Vision, Sept. 26-30, 2011, Moscow, Russ., 2011, pp. 111–114.
Рецензия
Для цитирования:
Казаков К.А., Семенов В.А. Объектно-ориентированная среда для разработки приложений планирования движения. Труды Института системного программирования РАН. 2017;29(5):185-238. https://doi.org/10.15514/ISPRAS-2017-29(5)-11
For citation:
Kazakov K.A., Semenov V.A. Object-oriented framework for motion planning in complex dynamic environments. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(5):185-238. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(5)-11
Послать статью по эл. почте 