Authors V.V. Soloviev, I.O. Shapovalov, V.V. Shadrina
Month, Year 02, 2015 @en
Index UDC 620.9
Abstract The aim of the paper is to solve the problem of a vehicle motion planning in the environment with a priori uncertainty using a Voronoi diagram. For the problem solution, the analysis of some representative papers was carried out and confirmed that the vehicle motion planning in the environment with uncertain location of obstacles is a computationally expensive process. As a result, an algorithm for the environment mapping on the basis of data from the range finder mounted on the vehicle was proposed. This algorithm allows solution the problem of path planning in real time. The steps of the coordinate cauterization and linking with obstacles algorithm are presented. The modification of the coordinate cluster analysis using the intersection of polygons is proposed. A procedure of the sensor data analysis for the case of this data coincidence with the data in the coordinate database is considered. We also considered the following basic modes of the vehicle motion in the environment: the motion between the obstacles, the motion on the left and on the right of obstacles, the motion without obstacles. The approach to obstacle avoidance based on the adding of coordinates of extreme points belonging to the same object is shown. The motion between the obstacles along the edge of the Voronoi diagram corresponding to the case of incomplete road map is considered. Simulation of some basic modes was carried out for the cases when the obstacle location is next to a goal and the obstacles are uniformly located in the environment. The obtained results approve efficiency of the proposed algorithms for solving the problem of the safe vehicle motion in the environment with obstacles.

Download PDF

Keywords Planning of a path; Voronoi diagram; mapping of the environment; independent mobile objects.
References 1. Borenstein J., Koren Y. The Vector Field Histogram – fast obstacle avoidance for mobile robots, IEEE Journal of Robotics and Automation, 1991, Vol. 7, No. 3, pp. 278-288.
2. Guzik V.Ph., Chernukhin Yu.V., Pyavchenko A.O., Polenov M.Yu., Pereverzev V.A. and Saprykin R.V. Neural network method of intellectual planning of mobile robotic object movement in the conditions of uncertainty, Advances in Robotics, Mechatronics and Circuits. Proceedings of the 18th International Conference on Circuits (part of CSCC '14) and the 2014 International Conference on Mechatronics and Robotics, Structural Analysis (MEROSTA 2014). Santorini Island, Greece, 2014, pp. 194-200.
3. Bekasov D.E. Primenenie apparata nechetkoy logiki pri reshenii zadachi poiska puti v neizvestnom okruzhenii [The use of fuzzy logic in solving the problem of finding your way in an unknown environment], Elektronnyy zhurnal Molodezhnyy nauchno-tekhnicheskiy vestnik [Youth Scientific and Technical Bulletin]. Available at: (Accessed 12 April 2012).
4. Rigatos G.G., Tzafestas C.S., and Tzafestas S.G. Mobile robot motion control in partially unknown environments using a sliding‐mode fuzzy logic controller, Robotics and Autonomous Systems, 2000, Vol. 33, pp. 1-11.
5. Khatib O. Real-time obstacle avoidance for manipulators and mobile robots, IEEE Int. Conf. Robotics and Automation, 1985, pp. 500-505.
6. Masehian E., Amin-Naseri M.R. A Voronoi diagram-visibility graph-potential field compound algorithm for robot path planning, J. Robot Syst., 2004, Vol. 21, No. 6, pp. 275-300.
7. Minguez J., Montano L. Abstracting any Vehicle shape and the Kinematics and Dynamic Constraints from Reactive Collision Avoidance Methods, Autonomous Robotics, 2006, Vol. 20, No. 1, pp. 43-59.
8. Budanov V.M., Devyanin E.A. O dvizhenii kolesnykh robotov [On motion of wheeled robots], Prikladnaya matematika i mekhanika [Applied Mathematics and Mechanics], 2003, Vol. 67, Issue 2, pp. 244-255.
9. Pshikhopov V.Kh., Medvedev M.Yu. Upravlenie podvizhnymi ob"ektami v opredelennykh i neopredelennykh sredakh [Management of moving objects in certain and uncertain environments]. Moscow: Nauka, 2011, 350 p.
10. Nolborio H., Naniwa T., Arimoto S. A quadtree-based path-planning algorithm for a mobile robot, J. Robot Syst., 1990, Vol. 7, No. 4, pp. 555-574.
11. Amato N., Wu Y. A randomized roadmap method for path and manipulation planning, In Proc. IEEE Int. Conf. Robotics and Automation, 1996, Vol. 1, pp. 113-120.
12. Kedem K., Sharir M. An efficient motion planning algorithm for a convex rigid polygonal object in 2-dimensional polygonal spac, Discrete Comput. Geom., 1990, Vol. 5, No. 1, pp. 43-75.
13. Kim J., Pearce R.A., Amato N.M. Extracting optimal paths from roadmaps for motion planning, In Proc. IEEE Int. Conf. Robotics and Automation, 2003, Vol. 2, pp. 2424-2429.
14. La Valle S.M. Rapidly-Exploring Random Trees: A New Tool for Path Planning, Computer Science Dept., 1998, pp. 1-4.
15. Bhattacharya P., Gavrilova M.L., Roadmap-Based Path Planning Using the Voronoi Diagram for a Crearance-Based Shortest Path, IEEE Robotics & Automation Magazine, 2008, Vol. 15, No. 2, pp. 58-66.
16. Guibas L.J., Knuth D.E., and Sharir M. ‘Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica, 1992, Vol. 7, No. 1, pp. 381-413.
17. Kimberling C. Central Points and Central Lines in the Plane of a Triangle, Math. Mag., 1994, Vol. 67, pp. 163-187.
18. Kim J., Zhang F., Egerstedt M. A provably complete exploration strategy by constructing Voronoi diagrams, Autonomous Robots, 2010, Vol. 29, No. 3, pp. 367-380.
19. Seda M., Pich V. Robot motion planning using generalized Voronoi diagrams, Proceedings of 8th WSEAS International Conference on Signal Processing, Computational Geometry and Artificial Vision, Greese, 2008, pp. 215-220.
20. Weiler K., Atherton P. Hidden surface removal using polygon area sorting, Proceedings of the 4th annual conference on Computer graphics and interactive techniques, 1977, pp. 214-222.
21. de Berg M., van Kreveld M., Overmars M., Schwarzkopf O. Computational Geometry: Algorithms and Applications. Springer, 2000, 368 p.
22. Beloglazov D.A., Guzik V.F., Kosenko E.Yu., Krukhmalev V.A., Medvedev M.Yu., Pereverzev V.A., Pshikhopov V.Kh., P'yavchenko O.A., Saprykin R.V., Solov'ev V.V., Finaev V.I., Chernukhin Yu.V., Shapovalov I.O. Intellektual'noe planirovanie traektoriy podvizhnykh ob"ektov v sredakh s
prepyatstviyami [Intelligent planning of trajectories of moving objects in environments with obstacles], Under edition V.Kh. Pshikhopova. Moscow: Fizmatlit, 2014, 450 p.

Comments are closed.