Mathematics – Algebraic Topology
Scientific paper
2004-06-18
Mathematics
Algebraic Topology
Scientific paper
A topological theory initiated recently by the author uses methods of algebraic topology to estimate numerically the character of instabilities arising in motion planning algorithms. The present paper studies random motion planning algorithms and reveals how the topology of the robot's configuration space influences their structure. We prove that the topological complexity of motion planning TC(X) coincides with the minimal n such that there exists an n-valued random motion planning algorithm for the system; here $X$ denotes the configuration space. We study in detail the problem of collision free motion of several objects on a graph G. We describe an explicit motion planning algorithm for this problem. We prove that if G is a tree and if the number of objects is large enough, then the topological complexity of this motion planning problem equals 2m(G)+1 where m(G) is the number of the essential vertices of G. It turns out (in contrast with the results on the collision free control of many objects in space obtained earlier jointly with S. Yuzvinsky) that the topological complexity is independent of the number of particles.
No associations
LandOfFree
Collision Free Motion Planning on Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Collision Free Motion Planning on Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Collision Free Motion Planning on Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-203758