Efficient routing of multi-vehicle systems: Limited sensing and nonholonomic motion constraints

Consider a routing problem for a team of agents in the plane: target points appear over time in a bounded environment and must be visited by one of the agents. It is desired to minimize the expected waiting time between the appearance of a target point, and the instant it is visited.;In an effort to address issues relevant in applications such as autonomous mobile robotics, this dissertation focuses on variations of such a problem. First, we consider a team of agents that can only detect targets by way of limited-range onboard sensors. When the sensing radius is small, the system time is dominated by the searching component, and performance decreases dramatically due to the lack of information gathering capability demonstrated by the agents. However, when targets appear frequently, the presented algorithms recover the optimal performance achieved by agents with full information of the environment.;The main contribution of the dissertation lies in the second part, in which we return to a full-information setting, but consider a team of Uninhabited Aerial Vehicles (UAVs), modeled as vehicles moving with constant forward speed along paths of bounded curvature. We focus on the case in which targets appear sporadically. For holonomic agents (single integrators), this reduces to a facility location problem. If the density of UAVs in the environment is low, the optimal algorithm resembles that of holonomic agents: the environment is partitioned into static regions of dominance within which each agent is responsible for targets (territorial behavior). But if the density of UAVs is high, the optimal algorithm exhibits a gregarious behavior: the agents move in a coordinated pattern, each visiting targets that appear immediately in front of it. The above results demonstrate a phase transition in the optimal algorithm. We present a non-dimensional parameter that characterizes the phase and analyze the critical value at which the transition occurs. This analysis offers guidelines for system architects, control algorithm designers, and operators aiming to maximize the performance of their autonomous-vehicle systems.