Real-Time Robot Path Planning for Dynamic Obstacle Avoidance
Konstantinos Charalampous, Ioannis Kostavelis, Angelos Amanatiadis and Antonios Gasteratos
In this paper we present a method based on Cellular Automata (CA) rules, suitable for path planning in dynamically changing environments. The algorithm underlaying this method is the A* search one in combination with CAs, the discrete nature of which renders the method appropriate for both robot and obstacle state spaces. Moreover, the finite properties of the A* algorithm were amalgamated with the CA rules to built up a substantial search strategy. The proposed algorithm assures a collision-free cost-efficient path to target with optimal computational cost. The algorithm’s main attribute is that it expands the map state space with respect to time using adaptive time intervals to predict the potential expansion of obstacles, assuring a safe and minimum cost path. The proposed method has been examined in real world planar environments and exhibits remarkable performance, thus it can be applied to any arbitrary shaped obstacle.
Keywords: Robot path planning, obstacle avoidance, dynamic obstacles, cellular automata, laser scanner, 3D point cloud