Properties of motion planning algorithms
Published:
Properties of motion planning algorithms
Completeness
- If a solution exists, planner the algorithm always finds a solution
- If no solution exists, terminates and reports failure
Optimality
- Given a cost function for evaluating a sequence of actions, planner always returns a feasible sequence of actions with minimal cost
Example A*
Q. is a* complete?
A. yes
Q. is a* optimal?
A. It’s up to the heuristic function. If below conditions are met, then the a* is optimal
- the branching factor is finite
- arc costs are strictly positive
- if the heuristic is admissible