Path planning for car-like robots using global analysis and local evaluation

Presented is a new motion planning strategy using global analysis and local evaluation for car-like robots subject to non-holonomic constraints. The strategy keeps the original problem in 2D and deals with it in the workspace. It starts from globally analyzing the workspace to build Visibility Graph and find valid paths for a point robot. The free space evaluation is made along one of the point paths. Finally robot configurations are placed in the evaluated free space, and lemmas are introduced to ensure that robot travelling free of collision in direct, indirect or reversal manoeuvres. The strategy runs in time O(nk+nlogn) for k obstacles and n vertices. It has been extensively tested in computer simulations, demonstrating the versatility of the algorithm.