A Cell Decomposition Approach to Autonomous Path Planning for Directional Mobile Sensors
A methodology based on integer programming and cell decomposition is developed for planning the path of UGVs equipped with directional sensors used to classify multiple targets in an obstacle-populated environment. While it is desirable to solve this problem in minimum time, the non-completeness of the connectivity graph and the classification objectives do not allow for a Traveling Salesman Problem (TSP) solution. Moreover, the TSP is known to be NP hard. Therefore, this thesis presents an approach for decomposing the UGV workspace based on the directional sensor FOV, line-of-sight visibility and obstacle map. By this approach, a connectivity graph with observation cells can be obtained and an optimal path can be computed via integer programming. Simulations conducted in Webots, a professional robot simulator that supports accurate simulation of rigid body dynamics and sensors with computer vision capability, demonstrate the effectiveness of this approach compared to the "nearest neighbor" methods and classical TSP formulations.
Cell decomposition; Directional sensor; Minimum time; Path planning; Mechanical engineering
Knepper, Ross A.
M.S., Mechanical Engineering
Master of Science
dissertation or thesis