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

Savvas Sadiq Ali, Farhad Nawaz

Permalink

https://hdl.handle.net/2142/110706 Copy

Description

Title

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

Author(s)

Savvas Sadiq Ali, Farhad Nawaz

Issue Date

2021-04-23

Director of Research (if dissertation) or Advisor (if thesis)

Ornik, Melkior

Department of Study

Aerospace Engineering

Discipline

Aerospace Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

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

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.

Graduation Semester

2021-05

Type of Resource

Thesis

Permalink

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

Copyright and License Information

Copyright 2021 Farhad Nawaz Savvas Sadiq Ali

Owning Collections