Completeness and Performance
A motion planner is said to be complete if the planner in finite time either produces a solution or correctly reports that there is none. Most complete algorithms are geometry-based. The performance of a complete planner is assessed by its computational complexity.
Resolution completeness is the property that the planner is guaranteed to find a path if the resolution of an underlying grid is fine enough. Most resolution complete planners are grid-based. The computational complexity of resolution complete planners is dependent on the number of points in the underlying grid, which is O(1/hd), where h is the resolution (the length of one side of a grid cell) and d is the configuration space dimension.
Probabilistic completeness is the property that as more “work” is performed, the probability that the planner fails to find a path, if one exists, asymptotically approaches zero. Several sample-based methods are probabilistically complete. The performance of a probabilistically complete planner is measured by the rate of convergence.
Incomplete planners do not always produce a feasible path when one exists. Sometimes incomplete planners do work well in practice.
Read more about this topic: Motion Planning
Famous quotes containing the words completeness and, completeness and/or performance:
“Poetry presents indivisible wholes of human consciousness, modified and ordered by the stringent requirements of form. Prose, aiming at a definite and concrete goal, generally suppresses everything inessential to its purpose; poetry, existing only to exhibit itself as an aesthetic object, aims only at completeness and perfection of form.”
—Richard Harter Fogle, U.S. critic, educator. The Imagery of Keats and Shelley, ch. 1, University of North Carolina Press (1949)
“Poetry presents indivisible wholes of human consciousness, modified and ordered by the stringent requirements of form. Prose, aiming at a definite and concrete goal, generally suppresses everything inessential to its purpose; poetry, existing only to exhibit itself as an aesthetic object, aims only at completeness and perfection of form.”
—Richard Harter Fogle, U.S. critic, educator. The Imagery of Keats and Shelley, ch. 1, University of North Carolina Press (1949)
“The honor my country shall never be stained by an apology from me for the statement of truth and the performance of duty; nor can I give any explanation of my official acts except such as is due to integrity and justice and consistent with the principles on which our institutions have been framed.”
—Andrew Jackson (1767–1845)