Reactive path-planning: a directional diffusion algorithm on multilayered cellular automata

Cellular Automata model is a powerful instrument used in many applications. In this paper we present a Reactive Path-Planning Algorithm for a non-holonomic robot moving on a 2D surface based on Multilayered Cellular Automata. The robot considered has a preferential motion direction and has to move using smoothed trajectories, without stopping and turning in place, and with a minimum steering radius. We have implemented a new algorithm based on a directional (anisotropic) propagation of repulsive and attracting potential values in a Multilayered Cellular Automata model. The algorithm finds all the optimal trajectories following the minimum valley of a potential hypersurface embedded in a 4D space, built respecting the imposed constraints. Our approach results to be distributed and incremental: whenever changing the initial or the final pose, or the obstacles distribution, the automata start evolving towards a new global steady state, looking for a new set of solutions. Because it reacts to obstacles distribution changes, it can be also used in unknown or dynamical environments in combination with a world modeler. The path-planning algorithm is applicable on a wide class of vehicles kinematics, selected changing a set of weights