Interval Methods for Optimal and Guaranteed Path Planning

Описание: Speaker:
Lucas Si Larbi (Université Paris Saclay, CEA, List, Palaiseau, and ENSTA, Institut Polytechnique de Paris, Palaiseau, France)

Abstract:
The transition from global to local planning often represents a significant gap in outdoor navigation. The local path planner must allow for any unforeseen environmental constraints, such as new obstacles detected in the vicinity of the robot. The solution suggested here, to fill this gap, consists in generating a path optimized over a receding horizon, based on waypoints generated by the global planner. This path is then followed by using a model-based predictive controller. Our optimal local planner uses an interval branch and bound algorithm to optimize successive connected uniform interval B-spline curves. Such curves are widely used in computer aided design, computer graphics, and robotics for their powerful properties: a local modification; a definition of the entire curve only with several control points; a setting of the degree of continuity of the curve. A natural way to bound these curves is to consider both the parameter and control points as intervals. However, as they are constructed from a sum of polynomial basis functions, and, as the pessimism of the natural interval evaluation is cumulative, the resulting bounds are often worthless. It is therefore necessary to bound basis functions with other approaches. In this talk, we propose a comprehensive analysis of interval extensions of B-spline curves. We also present our local planning, its implementation, demonstrations in simulation and finally a real-life experiment with a wheeled differential robot.