Real-time path planning for navigation in unknown environment

Real-time path planning is a challenging task that has many applications in the fields of AI, moving robots, virtual reality, agent behavior simulation, and action games. The various approaches for path planning have different criteria that have to be met, resulting in a number of algorithms for solutions to specific problems. In this paper, we introduce our approach and recent development regarding path planning in game environments. We propose a real-time motion-optimization algorithm called Adaptive Dynamic Points of Visibility (ADPV) for navigation of vehicles or moving agents in dynamical unconfigured environments, which computes a collision-free, time-optimal motion track for the moving objects. Our approach is able to deal with the obstacle-space that is unknown or partially unknown to the moving agent. It therefore solves the drawbacks of traditional obstacle-space configuration methods.

1. Introduction

Navigation has become a subject of significant interest in the last twenty years because it is open to a broad range of possible applications. Solutions of path planning algorithm have been proposed since the 1970s. A path planning algorithm among polyhedral obstacles based on the geometry graph was proposed in 1979 [1], and then, later extended to the Configuration Space approach. The algorithm proposed could generate very precise optimal trajectories and solve really difficult problems, especially in cluttered worlds, also taking into account non-homonymic constraints, but they are very time consuming [2], as the updating phase of the world model becomes a relevant part of the navigation. The information concerned with the environment plays a key role in all navigation algorithms. Once we have the accurate map description about the space, it will be easier to design a reasonable path.