L*: An intelligent path planning algorithm based on renormalized measure of probabilistic regular languages

Abstract

A novel path planning algorithm L* is introduced that reduces the problem to optimization of a probabilistic finite state machine and applies the rigorous theory of language-measure-theoretic optimal control to compute v-optimal paths to the specified goal. It is shown that although the underlying navigation model is probabilistic, the proposed algorithm computes plans that can be executed in a deterministic sense with automated optimal trade-off between path length and robustness under dynamic uncertainty. The algorithm has been validated on mobile robotic platforms in a laboratory environment.