Optimisation based path planning for car parking in narrow environments

• Path is calculated by solving several local static optimisation problems iteratively.
• Driving direction changes are locally determined based on simple rules.
• Obtained paths are similar to manoeuvres of a human driver.
• Tree-based extension guides the local planner efficiently.
• High rate of success in narrow environments with low computing costs.

In the last decades, a large variety of robot motion planners emerged. However, manoeuvring in very narrow environments, e.g., for common parking scenarios, cannot be reliably handled with existing path planners at low computing costs. This is why, this paper presents a fast optimisation based path planner which specialises on narrow environments. In the proposed approach, the kinematic differential equations are discretised. For the resulting discrete path segments, a static optimisation problem is formulated to determine the path independently of the considered scenario. In each iteration step, the path length is also optimised to handle close distances to the obstacles as well as longer driving distances. Due to the local nature heuristic rules for driving direction changes are formulated which intend to imitate the behaviour of a human driver. The drawback of the local nature is the lack of global information to handle scenarios with obstacles blocking the path. To overcome this problem, a tree-based guidance for the local planner is introduced. The landmarks for the tree are implicitly created by the local planner allowing an efficient exploration of the free configuration space. The performance of the algorithm is evaluated utilising Monte-Carlo simulations and compared to state-of-the-art path planning algorithms.