{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/110706"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/110706","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Multi-agent, multi-objective path planning in complex environments","abstract":"Path planning for autonomous missions often involves dynamic, uncertain and complex environments such as robots operating on planetary bodies, in underwater regions and in adverse weather conditions. Path planning in such conditions demands the use of control frameworks significantly different from the available methods for simple environments. In the first part of the thesis, we consider a generalized problem of visiting a set of targets while avoiding some obstacles, but the location of targets and obstacles are a priori unknown. We present the environment as a labeled graph where the labels of states are initially unknown, and consider a motion planning objective to fulfill a combination of reach-avoid specifications given on these labels in minimum time. By describing the record of visited labels as an automaton, we translate our problem to a Canadian traveler problem on an adapted state space. We propose a strategy that exploits possible a priori knowledge about the labels and the environment and incrementally reveals the environment online. Namely, the agent plans, follows, and replans the optimal path by assigning edge weights that balance exploration and exploitation, given the current knowledge of the environment. We illustrate our strategy on the setting of an agent operating in a gridwold environment. In the second part, we consider the problem of visiting a set of targets in minimum time by a single agent or a team of non-communicating agents in a complex environment with stochastic dynamics. We model the environment by a Markov decision process. First, for the single-agent case, we reduce our problem to a Hamiltonian path problem and show that it is at least NP-hard. Using Bellman's optimality equation, we present an optimal algorithm that is exponential in the number of target states. Then, we trade-off optimality for time complexity by presenting an algorithm that is polynomial at each time step. We prove that the proposed algorithm generates optimal policies for certain classes of Markov decision processes. For the multi-agent case, we propose a heuristic partitioning procedure of assigning targets to agents that approximately minimizes the largest expected time to visit the target states. We prove that the heuristic procedure generates optimal partitions for clustered target states. We present the performance of our algorithms on random Markov decision processes and a grid world environment inspired by autonomous underwater vehicles operating in an ocean.","abstract_html":"Path planning for autonomous missions often involves dynamic, uncertain and complex environments such as robots operating on planetary bodies, in underwater regions and in adverse weather conditions. Path planning in such conditions demands the use of control frameworks significantly different from the available methods for simple environments. In the first part of the thesis, we consider a generalized problem of visiting a set of targets while avoiding some obstacles, but the location of targets and obstacles are a priori unknown. We present the environment as a labeled graph where the labels of states are initially unknown, and consider a motion planning objective to fulfill a combination of reach-avoid specifications given on these labels in minimum time. By describing the record of visited labels as an automaton, we translate our problem to a Canadian traveler problem on an adapted state space. We propose a strategy that exploits possible a priori knowledge about the labels and the environment and incrementally reveals the environment online. Namely, the agent plans, follows, and replans the optimal path by assigning edge weights that balance exploration and exploitation, given the current knowledge of the environment. We illustrate our strategy on the setting of an agent operating in a gridwold environment. In the second part, we consider the problem of visiting a set of targets in minimum time by a single agent or a team of non-communicating agents in a complex environment with stochastic dynamics. We model the environment by a Markov decision process. First, for the single-agent case, we reduce our problem to a Hamiltonian path problem and show that it is at least NP-hard. Using Bellman's optimality equation, we present an optimal algorithm that is exponential in the number of target states. Then, we trade-off optimality for time complexity by presenting an algorithm that is polynomial at each time step. We prove that the proposed algorithm generates optimal policies for certain classes of Markov decision processes. For the multi-agent case, we propose a heuristic partitioning procedure of assigning targets to agents that approximately minimizes the largest expected time to visit the target states. We prove that the heuristic procedure generates optimal partitions for clustered target states. We present the performance of our algorithms on random Markov decision processes and a grid world environment inspired by autonomous underwater vehicles operating in an ocean.","abstract_has_math":false,"creators":["Savvas Sadiq Ali, Farhad Nawaz"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Aerospace Engineering","degree_department":null,"school":null,"contributors":["Ornik, Melkior"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-09-17T02:34:39Z","date_published":"2021-09-17T02:34:39Z","updated_at":"2026-07-22T22:24:52Z","subjects":["Autonomous systems, Path planning, Markov decision processes, Linear temporal logic, Automata"],"languages":["en"],"rights":["Copyright 2021 Farhad Nawaz Savvas Sadiq Ali"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/110706","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ornik, Melkior"]},{"key":"dc:creator","label":"Author","values":["Savvas Sadiq Ali, Farhad Nawaz"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-09-17T02:34:39Z","2023-09-17T02:34:57Z","2021-04-23","2021-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Aerospace Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Autonomous systems, Path planning, Markov decision processes, Linear temporal logic, Automata"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Farhad Nawaz Savvas Sadiq Ali"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/110706"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Path planning for autonomous missions often involves dynamic, uncertain and complex environments such as robots operating on planetary bodies, in underwater regions and in adverse weather conditions. Path planning in such conditions demands the use of control frameworks significantly different from the available methods for simple environments. In the first part of the thesis, we consider a generalized problem of visiting a set of targets while avoiding some obstacles, but the location of targets and obstacles are a priori unknown. We present the environment as a labeled graph where the labels of states are initially unknown, and consider a motion planning objective to fulfill a combination of reach-avoid specifications given on these labels in minimum time. By describing the record of visited labels as an automaton, we translate our problem to a Canadian traveler problem on an adapted state space. We propose a strategy that exploits possible a priori knowledge about the labels and the environment and incrementally reveals the environment online. Namely, the agent plans, follows, and replans the optimal path by assigning edge weights that balance exploration and exploitation, given the current knowledge of the environment. We illustrate our strategy on the setting of an agent operating in a gridwold environment. In the second part, we consider the problem of visiting a set of targets in minimum time by a single agent or a team of non-communicating agents in a complex environment with stochastic dynamics. We model the environment by a Markov decision process. First, for the single-agent case, we reduce our problem to a Hamiltonian path problem and show that it is at least NP-hard. Using Bellman's optimality equation, we present an optimal algorithm that is exponential in the number of target states. Then, we trade-off optimality for time complexity by presenting an algorithm that is polynomial at each time step. We prove that the proposed algorithm generates optimal policies for certain classes of Markov decision processes. For the multi-agent case, we propose a heuristic partitioning procedure of assigning targets to agents that approximately minimizes the largest expected time to visit the target states. We prove that the heuristic procedure generates optimal partitions for clustered target states. We present the performance of our algorithms on random Markov decision processes and a grid world environment inspired by autonomous underwater vehicles operating in an ocean.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2023-05-01","The student, Farhad Nawaz Savvas Sadiq Ali, accepted the attached license on 2021-04-21 at 08:29.","The student, Farhad Nawaz Savvas Sadiq Ali, submitted this Thesis for approval on 2021-04-21 at 08:36.","This Thesis was approved for publication on 2021-04-23 at 15:51.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16448 on 2021-09-16 at 17:04:10","Made available in DSpace on 2021-09-17T02:34:39Z (GMT). No. of bitstreams: 2 SAVVASSADIQALI-THESIS-2021.pdf: 1383870 bytes, checksum: b0d6963427e3e2c9ab98ec830c0c3ffc (MD5) LICENSE.txt: 4226 bytes, checksum: f0bee0e578175a99cd19e0ffbb305b99 (MD5) Previous issue date: 2021-04-23","Embargo set by: Seth Robbins for item 118549 Lift date: 2023-09-17T02:34:57Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Multi-agent, multi-objective path planning in complex environments"]}]}],"canonical_facts":{"dc:contributor":["Ornik, Melkior"],"dc:creator":["Savvas Sadiq Ali, Farhad Nawaz"],"dc:date":["2021-09-17T02:34:39Z","2023-09-17T02:34:57Z","2021-04-23","2021-05"],"dc:description":["Path planning for autonomous missions often involves dynamic, uncertain and complex environments such as robots operating on planetary bodies, in underwater regions and in adverse weather conditions. Path planning in such conditions demands the use of control frameworks significantly different from the available methods for simple environments. In the first part of the thesis, we consider a generalized problem of visiting a set of targets while avoiding some obstacles, but the location of targets and obstacles are a priori unknown. We present the environment as a labeled graph where the labels of states are initially unknown, and consider a motion planning objective to fulfill a combination of reach-avoid specifications given on these labels in minimum time. By describing the record of visited labels as an automaton, we translate our problem to a Canadian traveler problem on an adapted state space. We propose a strategy that exploits possible a priori knowledge about the labels and the environment and incrementally reveals the environment online. Namely, the agent plans, follows, and replans the optimal path by assigning edge weights that balance exploration and exploitation, given the current knowledge of the environment. We illustrate our strategy on the setting of an agent operating in a gridwold environment. In the second part, we consider the problem of visiting a set of targets in minimum time by a single agent or a team of non-communicating agents in a complex environment with stochastic dynamics. We model the environment by a Markov decision process. First, for the single-agent case, we reduce our problem to a Hamiltonian path problem and show that it is at least NP-hard. Using Bellman's optimality equation, we present an optimal algorithm that is exponential in the number of target states. Then, we trade-off optimality for time complexity by presenting an algorithm that is polynomial at each time step. We prove that the proposed algorithm generates optimal policies for certain classes of Markov decision processes. For the multi-agent case, we propose a heuristic partitioning procedure of assigning targets to agents that approximately minimizes the largest expected time to visit the target states. We prove that the heuristic procedure generates optimal partitions for clustered target states. We present the performance of our algorithms on random Markov decision processes and a grid world environment inspired by autonomous underwater vehicles operating in an ocean.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2023-05-01","The student, Farhad Nawaz Savvas Sadiq Ali, accepted the attached license on 2021-04-21 at 08:29.","The student, Farhad Nawaz Savvas Sadiq Ali, submitted this Thesis for approval on 2021-04-21 at 08:36.","This Thesis was approved for publication on 2021-04-23 at 15:51.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16448 on 2021-09-16 at 17:04:10","Made available in DSpace on 2021-09-17T02:34:39Z (GMT). No. of bitstreams: 2 SAVVASSADIQALI-THESIS-2021.pdf: 1383870 bytes, checksum: b0d6963427e3e2c9ab98ec830c0c3ffc (MD5) LICENSE.txt: 4226 bytes, checksum: f0bee0e578175a99cd19e0ffbb305b99 (MD5) Previous issue date: 2021-04-23","Embargo set by: Seth Robbins for item 118549 Lift date: 2023-09-17T02:34:57Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/110706"],"dc:language":["en"],"dc:rights":["Copyright 2021 Farhad Nawaz Savvas Sadiq Ali"],"dc:subject":["Autonomous systems, Path planning, Markov decision processes, Linear temporal logic, Automata"],"dc:title":["Multi-agent, multi-objective path planning in complex environments"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Aerospace Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}