Single Agent and Multi-agent Path Planning in Unknown and Dynamic Environments

Abstract

As autonomous agents make the transition from solving simple, well-behaved problems to being useful entities in the real world, they must deal with the added complexity and uncertainty inherent in real environments. In particular, agents navigating through the real world can be confronted with imperfect information (e.g. when prior maps are absent or incomplete), limited deliberation time (e.g. when agents need to act quickly), and dynamic elements (e.g. when there are humans or other agents in the environment). This thesis addresses the problem of path planning and replanning in realistic scenarios involving these three challenges. For single agent planning we present a set of discrete search algorithms that efficiently repair the current solution when new information is received concerning the environment. We also introduce an approach that is able to provide better solutions through reasoning about the uncertainty in the initial information held by the agent. To cope with both imperfect information and limited deliberation time, we provide an additional algorithm that is able to improve the solution while time allows and repair the solution when new information is received. We further show how this algorithm can be used to plan and replan paths in dynamic environments. For multi-agent planning we present a set of sampling-based search algorithms that provide similar behavior to the above approaches but that can handle much higher dimensional search spaces. These sampling-based algorithms extend current approaches to perform efficient repair when new information is received and to provide higher quality solutions given limited deliberation time. We show how our culminating algorithm, which is able to both improve and repair its solution over time, can be used for multi-agent planning and replanning in dynamic environments. Together, the collection of planning algorithms introduced in this thesis enable single agents and multi-agent teams to navigate and coordinate in a wide range of realistic scenarios.