Comparing Path Length by Boundary Following Fast Matching Method and Bug Algorithms for Path Planning. Opportunities and Challenges for Next-Generation Artificial Intelligence

Abstract. Local or sensor-based path planning in an unknown environment is a challenging problem for mobile robots. In completely known grid environments, the shortest Euclidean-length path connecting a given start-goal point pair can be generated using the Fast Marching Method (FMM). In contrast, in unknown envi-ronments, path planning must be reactive (i.e. based on recent sensory information) and boundary following (BF) is one type of reactive path planning technique. In [1], a hybrid method called Boundary Following FMM (BFFMM) was proposed that could extend the applicability of FMM to work well in an unknown environ-ment using only local sensory perceptions. Bug algorithms are one family of navigation algorithms that also utilize BF technique in planning paths in unknown environments. This paper compares the path length of the paths generated by BFFMM with those by Bug1 and Bug2, the earliest versions of the Bug family algorithms to quantitatively reveal the effects of environment uncertainties on length of paths generated by navigation methods using boundary following. By comparison, BFFMM is a modest mobile robot path planner that bridges the gap between unknown and known terrain.