Back to search

Cornell University

A Cell Decomposition Approach to Autonomous Path Planning for Directional Mobile Sensors

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
M.S., Mechanical Engineering
Level thesis:degree_level
Master of Science
Discipline thesis:degree_discipline
Mechanical Engineering
Grantor
Cornell University
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liu, Zeyu
Chair dc:contributor.chair
  • Ferrari, Silvia
Committee member dc:contributor.committeemember
  • Knepper, Ross A.

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
10489529
Dc Identifier Other
ProQuest Submission ID: 10310
ProQuest Publication ID: 10821933

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Liu, Zeyu. A Cell Decomposition Approach to Autonomous Path Planning for Directional Mobile Sensors. Master of Science thesis, Cornell University, 2018. https://hdl.handle.net/1813/59444