Michigan Technological University
ALGORITHMS FOR COORDINATING MULTIPLE AUTONOMOUS VEHICLES UNDER VARIOUS CONSTRAINTS WITH EMPHASIS ON WORKLOAD BALANCING
Abstract
dc:description.abstractThis dissertation focuses on developing algorithms to solve the problem of coordinating multiple autonomous vehicles under various constraints, aiming to produce practical solutions for real-world applications. Built upon three journal publications addressing two coordination-related problems in different domains, this research document tackles the challenges of heterogeneity constraints and cable entanglement issues encountered by autonomous vehicle systems. The first problem tackles task allocation and path planning for heterogeneous ground mobile vehicles operating in a 2D environment with asymmetric travel costs. By enhancing previous Primal-Dual approximation heuristic methods, novel techniques are introduced to manipulate dual variables and achieve balanced workload distribution, ultimately minimizing the maximum tour cost. The second problem addresses the issue of tether entanglement faced by multiple tethered underwater vehicle systems navigating underwater. A multi-layer heuristic is developed by extending the Primal-Dual heuristic into a 3D environment and incorporating an additional algorithm layer to detect and resolve tether entanglements within a reasonable computation cost. Drawing on insights gained from these two problems, a new versatile algorithm has been developed that is applicable to a range of min-max Multiple Depot Heterogeneous Asymmetric Traveling Salesperson Problems (MDHATSPs). This novel heuristic offers enhanced computational efficiency and practicality by refining formulation and integrating critical constraints, such as cable entanglement. This dissertation has value in providing heuristics for routing problems that involve multiple autonomous vehicles with additional constraints. Each algorithm is developed from problem formulation and considered to improve solution qualities and computation time for implementation in real-world applications.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy in Mechanical Engineering-Engineering Mechanics (PhD)
- Level thesis:degree_level
- Open Access Dissertation
- Discipline thesis:degree_discipline
- Department of Mechanical Engineering-Engineering Mechanics
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Patil, Abhishek
- Committee members dc:contributor.committeemember
-
- Gordon Parker
- Seulchan Lee
- Contributors dc:contributor
-
- Jung Yun Bae
- Myoungkuk Park
Subjects
dc:subject × 5Rights
- Licence dc:rights.license
Identifiers
dc:identifier.*- Identifier
- https://digitalcommons.mtu.edu/etdr/1741