Motion planning algorithms for configuration spaces in the higher dimensional case

Ayşe Borat



The topological approach to the motion planning problem was introduced by Farber in \cite{F} and \cite{F2}. A motion planning problem is a rule assigning a continuous path to given two configurations - initial point and desired final point of a robot. Farber introduced the notion of topological complexity which measures the discontinuity of any motion planner in a configuration space. In \cite{Ru}, Rudyak introduced higher topological complexity, the concept fully developed in \cite{B}. Higher topological complexity is related to motion planning problem which assigns a continuous path (with $n$-legs) to given $n$ configurations. More precisely, it can be understood as a motion planning algorithm when a robot travels from the initial point $A_{1}$ to $A_{2}$, then from $A_{2}$ to $A_{3}$, and this keeps going until it reaches at the desired final point $A_{n}$. 

This paper is based on the work of Mas-Ku and Torres-Giese who gave an explicit motion planning algorithm for configuration spaces $F(\mathbb{R}^{2},k)$ and $F(\mathbb{R}^{n},k)$, in \cite{MT}. In the last section, we will consider the higher dimensional case in the sense of Rudyak in \cite{Ru}, and give an explicit motion planning algorithm for this case.


Motion planning algorithm; configuration spaces

Full Text:



I. Basabe, J. Gonzalez, Y. Rudyak and D. Tamaki, Higher topological complexity and its symmetrization, Algebraic and Geometric Topology 14 (2014), 2103–2124.

M. Farber, Instabilities of robot motion, Topology Appl. 140 (2004), 245–266.

M. Farber, Topological complexity of motion planning, Discrete Comput. Geom. 29 (2003), 211–221.

J. Gonzalez and M. Grant, Sequential motion planning of non-colliding particles in Euclidean spaces, Proc. Amer. Math. Soc. 143 (2015), 4503–4512.

H. Mas-Ku and E. Torres-Giese, Motion planning algorithms for configuration spaces, Bol. Soc. Mat. Mex., DOI 10.1007/s40590-014-0046-2.

Yu. Rudyak, On higher analogs of topological complexity, Topology Appl. 157 (2010), 916–920; Erratum: Topology Appl. 157 (2010), p. 1118.


  • There are currently no refbacks.

Partnerzy platformy czasopism