Probabilistic mapping of dynamic obstacles using Markov chains for replanning in dynamic environments

Robots acting in populated environments must be capable of safe but also time efficient navigation. Trying to completely avoid regions resulting from worst case predictions of the obstacle dynamics may leave no free space for a robot to move, especially in environments with high dynamic. This work presents an algorithm for a ldquosoftrdquo risk mapping of dynamic objects leaving the complete space free of static objects for path planning. Markov Chains are used to model the dynamics of moving persons and predict their potential future locations. These occlusion estimations are mapped into risk regions which serve to plan a path through potentially obstructed space searching for the trade-off between detour and time delay. The offline computation of the Markov Chain model keeps the computational effort low, making the approach suitable for online applications.