**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**32912

##### Robot Path Planning in 3D Space Using Binary Integer Programming

**Authors:**
Ellips Masehian,
Golnaz Habibi

**Abstract:**

**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.