Theses and Dissertations


Luo, Chaomin

Committee Member

Jones, Bryan

Committee Member

Luo, Yu

Date of Degree


Original embargo terms

Visible MSU only 1 year

Document Type

Graduate Thesis - Campus Access Only


Electrical and Computer Engineering

Degree Name

Master of Science (M.S.)


James Worth Bagley College of Engineering


Department of Electrical and Computer Engineering


With many robots now being developed for indoor settings, an autonomous mobile robot should be capable of reaching multiple targets within a dense, complex environment while maintaining the optimal path taken and avoiding all obstacles. In this thesis, we propose a global path planning algorithm that uses data created from a Generalized Voronoi Diagram (GVD) to traverse complex environments. The global route is made from the skeleton of the diagram that ensures the avoidance of static obstacles. Once this route is determined, dynamic programming is used to determine the optimal route to reach each target location while safely navigating obstacles in the map. A Dynamic Window Approach (DWA) local path planner is integrated into the algorithm to provide collision-free navigation in case of unexpected or dynamic obstacles that may be encountered during traversal. Our comprehensive simulations and comparative analyses highlight the proposed model’s robustness, demonstrating its ability to efficiently navigate to multiple targets through the shortest routes while adeptly circumventing obstacles. These findings validate the model’s effectiveness, confirming its superior performance in complex multi-target navigation scenarios and its capability to dynamically adapt to unforeseen obstacles, thereby illustrating a significant advancement in the field of autonomous indoor navigation.