Graph representation of n-dimensional space

Abstract

This paper investigates how graph representation can be created for the mesh which is a discrete approximation of n-dimensional continuous space. The paper discusses the relationship between mesh dimensionality and the type and quantity of edges connecting each vertex with its neighbors. Basing on the analysis, a simple algorithm is also proposed to create such graph representation. The purpose of the graph is to search optimal paths and trajectories in the represented space.

Keywords

Trajectory optimization / Path optimization / Graph search algorithms

References

[1.] LaValle SM, Jr Kuffner JJ. Randomized kinodynamic planning. Int J Robot Res, 2001, 20(5): 378-400.

[2.] Applegate DL, Bixby RE, Chvátal V et al (2011) The travelling salesman problem: a computational study. Princeton University Press, Princeton

[3.] Sánchez G, Latombe JC (2002) Using a PRM planner to compare centralized and decoupled planning for multi-robot system. In: IEEE international conference on robotics and automation, vol 2, pp 2112–2119

[4.] Carpin S. Randomized motion planning: a tutorial. Int J Robot Autom, 2006, 21(3): 184-195.

[5.] LaValle SM. Planning algorithms, 2006, Cambridge: Cambridge University Press.

[6.] Sukharev AG. Optimal strategies of the search for an extremum. USSR Comput Math Math Phys, 1971, 11(4): 910-924.

[7.] Gross JL, Yellen J (2003) Handbook of graph theory. CRC Press, Boca Raton

[8.] Hogben L (2013) Handbook of linear algebra. 2nd edn. Chapman and Hall/CRC, Boca Raton

[9.] Goodman JE, O’Rourke J (2004) Handbook of discrete and computational geometry. 2nd edn. Chapman and Hall/CRC, Boca Raton

[10.] Coxeter HSM (1973) Regular polytopes. 3rd edn. Dover Publications, New York

[11.] Lee J (2013) Introduction to topological manifolds. 2nd edn. Springer, New York

[12.] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agent. IEEE Trans Syst Man Cybern, 1996, 26(1): 29-41.