Completeness in robot motion planning

Abstract

this paper we consider the completeness of several algorithms in robot motion planning. The two conditions for completeness, finding a solution if it exists, and terminating otherwise, suggest a distinction between algorithms that satisfy the former but not the latter: we refer to these as "exact" algorithms and give examples. We then ask the stronger question: does a solution exist for all instances of a problem? We propose the term "solution-complete" to describe a property of problems and describe two recent results: a proof that a part feeding problem is solution-complete, and a proof that a fixturing problem is not solution-complete.