{"id":{"repo_id":"mtu","oai_identifier":"oai:digitalcommons.mtu.edu:etdr-2858"},"canonical_url":"https://search.ndltd.org/etd/mtu/oai:digitalcommons.mtu.edu:etdr-2858","repository":{"repo_id":"mtu","name":"Michigan Technological University","base_url":"https://digitalcommons.mtu.edu/do/oai/"},"display":{"title":"ALGORITHMS FOR COORDINATING MULTIPLE AUTONOMOUS VEHICLES UNDER VARIOUS CONSTRAINTS WITH EMPHASIS ON WORKLOAD BALANCING","abstract":"This 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.","abstract_html":"This 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.","abstract_has_math":false,"creators":["Patil, Abhishek"],"institution":null,"degree_name":"Doctor of Philosophy in Mechanical Engineering-Engineering Mechanics (PhD)","degree_level":"Open Access Dissertation","degree_discipline":"Department of Mechanical Engineering-Engineering Mechanics","degree_department":null,"school":null,"contributors":["Jung Yun Bae","Myoungkuk Park"],"advisors":[],"committee_chairs":[],"committee_members":["Gordon Parker","Seulchan Lee"],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T08:19:03Z","subjects":["Multi-Robot Systems; Task Allocation and Path Planning; Autonomous Navigation","Cable Entanglement Tethered AUVs","Marine Robotics","Operational Research","Robotics"],"languages":[],"rights":[],"rights_urls":["http://creativecommons.org/licenses/by/4.0/"],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.mtu.edu/etdr/1741"],"render_values":[{"text":"https://digitalcommons.mtu.edu/etdr/1741","href":"https://digitalcommons.mtu.edu/etdr/1741","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.37099/mtu.dc.etdr/1741","outbound_label":"DOI","outbound_source":"dc:identifier","record_url":"https://doi.org/10.37099/mtu.dc.etdr/1741","record_label":"Repository record","record_kind":"doi","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.mtu.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.mtu.edu%3Aetdr-2858","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jung Yun Bae","Myoungkuk Park"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Gordon Parker","Seulchan Lee"]},{"key":"dc:creator","label":"Author","values":["Patil, Abhishek"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2024-10-15T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2024-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Department of Mechanical Engineering-Engineering Mechanics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Open Access Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy in Mechanical Engineering-Engineering Mechanics (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Multi-Robot Systems; Task Allocation and Path Planning; Autonomous Navigation","Cable Entanglement Tethered AUVs","Marine Robotics","Operational Research","Robotics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights.license","label":"Dc Rights License","values":["http://creativecommons.org/licenses/by/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["10.37099/mtu.dc.etdr/1741","https://digitalcommons.mtu.edu/etdr/1741"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This 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."]},{"key":"dc:title","label":"Title","values":["ALGORITHMS FOR COORDINATING MULTIPLE AUTONOMOUS VEHICLES UNDER VARIOUS CONSTRAINTS WITH EMPHASIS ON WORKLOAD BALANCING"]}]}],"canonical_facts":{"dc:contributor":["Jung Yun Bae","Myoungkuk Park"],"dc:contributor.committeemember":["Gordon Parker","Seulchan Lee"],"dc:creator":["Patil, Abhishek"],"dc:date.available":["2024-10-15T07:00:00Z"],"dc:date.created":["2024-01-01T08:00:00Z"],"dc:description.abstract":["This 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."],"dc:identifier":["10.37099/mtu.dc.etdr/1741","https://digitalcommons.mtu.edu/etdr/1741"],"dc:rights.license":["http://creativecommons.org/licenses/by/4.0/"],"dc:subject":["Multi-Robot Systems; Task Allocation and Path Planning; Autonomous Navigation","Cable Entanglement Tethered AUVs","Marine Robotics","Operational Research","Robotics"],"dc:title":["ALGORITHMS FOR COORDINATING MULTIPLE AUTONOMOUS VEHICLES UNDER VARIOUS CONSTRAINTS WITH EMPHASIS ON WORKLOAD BALANCING"],"thesis:degree_discipline":["Department of Mechanical Engineering-Engineering Mechanics"],"thesis:degree_level":["Open Access Dissertation"],"thesis:degree_name":["Doctor of Philosophy in Mechanical Engineering-Engineering Mechanics (PhD)"]},"updated_at":"2026-11-19T08:19:03Z"}