Sampling-based planning for maximum margin input space obstacle avoidance

This paper proposes a method for safe navigation based on representative sample inputs. The representative inputs are chosen in safe input sets based on their distance from forbidden input sets. The inputs are not only the safest decisions with respect to various unmodeled sources of uncertainties, but are also representatives of groups of nearby input sets resulting in similar maneuvers. This approach provides an obstacle avoidance strategy for the maximum control margins. For computational efficiency, a sampling-based approach is adopted, and its performance in terms of solution quality and computation time is analyzed. The algorithm has been successfully demonstrated with an example of a car-like robot in fields with obstacles. For the multiple-step horizon problem, a best-first search algorithm is proposed with guarantee of optimality, and its computational efficiency is demonstrated.