top of page

IMOMD-RRT* System with
Geographical Information through
Multi-threaded Markov Clustering

Dongmyeong Lee, Jiunn-Kai Huang, Yingwen Tan, Vishnu Desaraju and Jessy W. Grizzle

Abstract

Informable Multi-Objective and Multi-Directional RRT* (IMOMD-RRT*) System is a fast algorithm for finding an initial path for multi-destination path planning problems. However, the IMOMD-RRT* System has trouble finding a better path as spanning trees explore because of randomness. This paper introduces a preprocessing method that finds geographically important nodes (i.e., bridges) through multi-threaded Markov clustering. The geographical information helps the system find a good initial path between destinations for IMOMD-RRT* System. Moreover, the proposed IMOMD-RRT* system can find a better path by sampling random nodes with the informed initial path. The system only samples the random points which have shorter heuristic distances than the current path distance.

bottom of page