Navigation among moving obstacles using the NLVO:: Principles and applications to intelligent vehicles

Vehicle navigation in dynamic environments is a challenging task, especially when the motion of the obstacles populating the environment is unknown beforehand and is updated at runtime. Traditional motion planning approaches are too slow to be applied in real-time to this problem, whereas reactive navigation methods have generally a too short look-ahead horizon. Recently, iterative planning has emerged as a promising approach, however, it does not explicitly take into account the movements of the obstacles. This paper presents a real-time motion planning approach, based on the concept of the Non-Linear Vobst (NLVO) (Shiller et al., 2001). Given a predicted environment, the NLVO models the set of velocities which lead to collisions with static and moving obstacles, and an estimation of the times-to-collision. At each controller iteration, an iterative A* motion planner evaluates the potential moves of the robot, based on the computed NLVO and the traveling time. Previous search results are reused to both minimize computation and maintain the global coherence of the solutions. We first review the concept of the NLVO, and then present the iterative planner. The planner is then applied to vehicle navigation and demonstrated in a complex traffic scenario.