Multi-agent, multi-objective path planning in complex environments

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Aerospace Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2021

Author dc:creator

• Savvas Sadiq Ali, Farhad Nawaz

Contributors dc:contributor

• Ornik, Melkior

• Autonomous systems, Path planning, Markov decision processes, Linear temporal logic, Automata

Statement dc:rights

• Copyright 2021 Farhad Nawaz Savvas Sadiq Ali

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/110706

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/110706