Randomised MPC-based motion-planning for mobile robot obstacle avoidance

This paper presents an algorithm for real-time sensor-based motion planning under kinodynamic constraints, in unknown environments. The objective of the trajectory-generation algorithm is to optimise a cost function out to a limited time horizon. The space of control trajectories is searched by expanding a tree using randomised sampling, in a manner similar to an RRT. The algorithm is improved by seeding the tree using the best control trajectory from the previous iteration, and by pruning branches based on a bound to the cost function and the best trajectory found so far. Performance of the algorithm is analysed in simulation. In addition, the algorithm has been implemented on two kinds of vehicles: the Segway RMP and a four-wheel-drive. The algorithm has been used to drive autonomously for a combined total on the order of hundreds of hours.