ISSN 2071-8594

Russian academy of sciences

Editor-in-Chief

Gennady Osipov

K.S. Yakovlev, D.A. Makarov, E.S. Baskin. UAV path planning technique under flight dynamics constraints

Abstract.

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 theoretically and empirically.

Keywords:

unmanned vehicle, unmanned aerial vehicle, intelligent control system, planning, angle-constrained path planning, heuristic search.

PP. 3-17.

Full version of the article in pdf.

REFERENCES

1. Osipov G.S., Tikhomirov I.A., Khachumov V.M., Yakovlev K.S. Intellektualnoe upravlenie transportnymi sredstvami: standarty, proekty, realizatsii // Aviakosmicheskoe priborostroenie. 2009. № 6. s. 34–43.
2. Yakovlev K.S., Makarov D.A., Panov A.I., Zubarev D.V. Printsipy postroeniya mnogourovnevykh arkhitektur sistem upravleniya bespilotnymi letatelnymi apparatami // Aviakosmicheskoe priborostroenie. 2013. № 4. s. 10-28.
3. Kendoul F. Survey of advances in guidance, navigation, and control of unmanned rotorcraft systems // Journal of Field Robotics. 2012. V. 29. №. 2. P. 315-378.
4. Yakovlev K.S., Petrov A.V., Khitkov V.V. Programmnyy kompleks navigatsii i upravleniya bespilotnymi transportnymi sredstvami // Informatsionnye tekhnologii i vychislitelnye sistemy. 2013. № 3. S. 72-83.
5. Yap P. Grid-based path-finding // Advances in Artificial Intelligence. Berlin Heidelberg: Springer, 2002. P. 44-55.
6. Yakovlev K. S. Grafy spetsialnoy struktury v zadachakh planirovaniya traektorii // Trudy III mezhdunarodnoy konferentsii «Sistemnyy analiz i informatsionnye tekhnologii SAIT-2009». 2009.
7. Wooden D. T. Graph-based path planning for mobile robots : dis. Georgia Institute of Technology. 2006.
8. Kavraki L. E. et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces // Robotics and Automation, IEEE Transactions on. 1996. V. 12. № 4. P. 566-580.
9. Yakovlev K.S., Baskin Ye.S. Grafovye modeli v zadache planirovaniya traektorii na ploskosti // Iskusstvennyy intellekt i prinyatie resheniy. 2013. №1. C. 5-12.
10. Dijkstra E.W. A note on two problems in connexion with graphs //Numerische mathematik. 1959. V.1. №. 1. P. 269-271.
11. Pearl J. Heuristics. Reading, Massachusetts: Addison-Wesley Publishing Company, 1984.
12. Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths // Systems Science and Cybernetics, IEEE Transactions on. 1968. V.4. №. 2. P. 100-107.
13. Korf R.E. Artificial intelligence search algorithms // CRC Handbook of Algorithms and Theory of Computation, M.J. Atallah (Ed.). Boca Raton, FL: CRC Press, 1998.
14. Variants of A* // [Elektronnyy resurs] URL:
http://theory.stanford.edu/~amitp/GameProgramming/Vari ations.html (data obrashcheniya: 20.08.2014).
15. Likhachev M., Stentz A. R* Search. // In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. Menlo Park, Calif. 2008
16. Yakovlev K.S. HGA*: effektivnyy algoritm planirovaniya traektorii na ploskosti // Iskusstvennyy intellekt i prinyatie resheniy. 2010. № 2. C. 16-25.
17. Latombe J. Robot Motion Planning. Boston: Kluwer Academic Publishers, 1991.
18. Kim H., Park B., Myung H. Curvature Path Planning with
High Resolution Graph for Unmanned Surface Vehicle // Robot Intelligence Technology and Applications. 2013. P. 147-154.
19. LaValle S. M., Kuffner Jr J. J. Rapidly-exploring random trees: Progress and prospects. In Algorithmic and Computational Robotics: New Directions. 2000.
20. Bertram D. et al. An integrated approach to inverse kinematics and path planning for redundant manipulators // Robotics and Automation, 2006. ICRA 2006. Proceedings 2006 IEEE International Conference on. 2006. P. 1874-1879.
21. Zhulev V.I., Leushkin V.S., Nguen T.N. Planirovanie lokalnoy traektorii avtomobilya-robota v realnom vremeni // Vestnik RGRTU. 2013. № 4 (46). Chast 3.
22. Korytov M.S. Avtomatizatsiya sinteza optimalnykh traektoriy peremeshcheniya gruzov mobilnymi gruzopodemnymi kranami v neodnorodnom organizovannom trekhmernom prostranstve. Omsk: SibADI, 2012. 380 s.
23. Haklay M., Weber P. Openstreetmap: User-generated street maps // Pervasive Computing. 2008. V. 7. №. 4. P. 12-18.
24. AscTec Nummingbird // [elektronnyy resurs] URL: http://www.asctec.de/en/uav-uas-drone-products/asctec-hummingbird/ (data obrashcheniya: 20.08.2014)
25. Lebedev A.A., Chernobrovkin L. S. Dinamika poleta. M.: Oborongiz, 1962
26. Schoellig A.P., Mueller F.L., D’Andrea R. Optimization- based iterative learning for precise quadrocopter trajectory tracking // Autonomous Robots. 2012. V.33. №.1-2. P.103-127.
27. Brescianini D., Hehn M., D'Andrea R. Quadrocopter pole acrobatics // Intelligent Robots and Systems (IROS), 2013 IEEE/RSJ International Conference. 2013. P. 3472-3479.
28. Bresenham J. E. Algorithm for computer control of a digital plotter //IBM Systems journal. 965. V. 4. №. 1. P. 25-30.
29. Daniel K. et al. Theta*: Any-angle path planning on grids
//Journal of Artificial Intelligence Research. 2010. V. 39. №. 1. P. 533-579.
30. Munoz P., Rodriguez-Moreno M. Improving efficiency in any-angle path-planning algorithms // Intelligent Systems (IS), 2012 6th IEEE International Conference. 2012. P. 213-218.
31. Pitteway M. L. V. Algorithms of conic generation // Fundamental algorithms for computer graphics. Springer Berlin Heidelberg, 1991. – S. 219-237.
32. Yakovlev, K., Baskin, E., & Hramoin, I. (2014). Fine-tuning Randomized Heuristic Search for 2D Path Planning: Finding the Best Input Parameters for R* Algorithm through Series of Experiments. In Artificial Intelligence: Methodology, Systems, and Applications (pp. 278-285). Springer International Publishing.