Robot Path Planning in 3D Space Using Binary Integer Programming

Authors: Ellips Masehian, Golnaz Habibi

Abstract:

This paper presents a novel algorithm for path planning of mobile robots in known 3D environments using Binary Integer Programming (BIP). In this approach the problem of path planning is formulated as a BIP with variables taken from 3D Delaunay Triangulation of the Free Configuration Space and solved to obtain an optimal channel made of connected tetrahedrons. The 3D channel is then partitioned into convex fragments which are used to build safe and short paths within from Start to Goal. The algorithm is simple, complete, does not suffer from local minima, and is applicable to different workspaces with convex and concave polyhedral obstacles. The noticeable feature of this algorithm is that it is simply extendable to n-D Configuration spaces.

Keywords: 3D C-space, Binary Integer Programming (BIP), Delaunay Tessellation, Robot Motion Planning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072461

References:

[1] F. Aurenhammer, and R. Klein, "Voronoi diagrams", in J. Sack and G. Urrutia (eds), Handbook of computational geometry, Elsevier Science Pub., 2000.
[2] Z. Bao, "Delaunay Triangulations and Voronoi Diagrams on Non-Planar Topologies," CS20c Final Report, California Institute of Technology, 1998, http://www.ugcs.caltech.edu/ ~jbao/Voronoi.pdf.
[3] J. F. Canny, "A Voronoi method for the piano movers- problem", in Proc. ICRA 1985, pp.530-535.
[4] J. F. Canny, The complexity of robot motion planning, The MIT press, Cambridge, Mass., 1988.
[5] B. Cetin, M. Bikdash, and F.Y. Hadaegh, "Hybrid mixed-logical linear programming algorithm for collision-free optimal path planning", IET Control Theory & Applications, 2007, Vol. 1, Issue 2, pp. 522-531.
[6] H. Choset, and J. Burdick, "Sensor-based exploration: the hierarchical generalized Voronoi graph", Int. J. of Robotics Research, Vol. 19, No. 2, (2000), pp. 96-125.
[7] H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, Boston, 2005.
[8] N. Christofides, A. Mingozzi, P. Toth, and C. Sandi, Combinatorial Optimization, John Wiley, 1979.
[9] C.Eldershaw," Heuristic Algorithms for robot motion planning,," Ph.D. Dissertation, the University of Oxford ,2001.
[10] Y. K. Hwang and N. Ahuja, "Gross motion planning - a survey", ACM Comp. Surveys, 24(3), (1992), pp. 219-291.
[11] J. M. Keil and J. R. Sack, "Minimum decompositions of polygonal objects" in G. T. Toussaint (ed.) Computational Geometry, North- Holland, Amsterdam, 1985, pp. 197-216.
[12] J. C. Latombe, Robot motion planning, Kluwer Academic publishers, London, 1991.
[13] G. Habibi, "Mobile Robot Path Planning Using Binary Integer Programming and Linear Matrix Inequalities (LMIs)," submitted to IEEE Int. Conf. Intell. Rob. Sys. (IROS) 2007
[14] N. S. V. Rao, N. Stolzfus, and S. S. Iyengar, "A ÔÇÿretraction- method for learned navigation in unknown terrains for a circular robot", IEEE Trans. Rob. Autom., Vol. 7, No. 5, (1991), pp. 699-707.
[15] O. Toupet, "Real-time path-planning using mixed integer linear programming and global cost-to-go maps", M.S. thesis, Dept. Aeronautics and Astronautics, MIT, February 2006.
[16] J. Vleugels and M. Overmars, "Approximating generalized Voronoi diagrams in any dimension," Technical report No. UU-CS-1995-14, Utrecht University, May 1995.
[17] Y. Wang and G. S. Chirikjian, "A new potential field method for robot path planning," in Proc. IEEE Int. Conf. Rob. Autom., 2000, pp. 977-982.