ν☆: a robot path planning algorithm based on renormalised measure of probabilistic regular languages

Abstract

Abstract This article introduces a novel path planning algorithm, called ν ☆, that reduces the problem of robot path planning to optimisation of a probabilistic finite state automaton. The ν ☆-algorithm makes use of renormalised measure ν of regular languages to plan the optimal path for a specified goal. Although the underlying navigation model is probabilistic, the ν ☆-algorithm yields path plans that can be executed in a deterministic setting with automated optimal trade-off between path length and robustness under dynamic uncertainties. The ν ☆-algorithm has been experimentally validated on Segway Robotic Mobility Platforms in a laboratory environment. Keywords: path planninglanguage measurediscrete event systemssupervisory control Acknowledgements This work has been supported in part by the US Army Research Office under Grant No. W911NF-07-1-0376 and the Office of Naval Research under Grant No. N00014-08-1-380.