Minimal Construct: Efficient Shortest Path Finding for Mobile Robots in Polygonal Maps

With the advent of polygonal maps finding their

way into the navigational software of mobile robots, the

Visibility Graph can be used to search for the shortest collision-

free path. The nature of the Visibility Graph-based shortest

path algorithms is such that first the entire graph is computed

in a relatively time-consuming manner. Then, the graph can

be searched efficiently any number of times for varying start

and target state combinations with the A* or the Dijkstra

algorithm. However, real-world environments are typically too

dynamic for a map to remain valid for a long time. With the

goal of obtaining the shortest path quickly in an ever changing

environment, we introduce a rapid path finding algorithm—

Minimal Construct—that discovers only a necessary portion

of the Visibility Graph around the obstacles that actually get

in the way. Collision tests are computed only for lines that

seem heuristically promising. This way, shortest paths can be

found much faster than with a state-of-the-art Visibility Graph

algorithm and as our experiments show, even grid-based A*

searches are outperformed in most cases with the added benefit

of smoother and shorter paths.