Active sensing with applications to mobile robotics.

Abstract

Compared to static sensors, mobile robots offer significant advantages primarily due to their ability to move and sense the world from multiple vantage points. However, they also pose significant challenges due to limitations on their resources. Specifically, moving a robot to a new location consumes energy, and thus, it is of paramount importance to design optimal motion strategies for mobile robots that maximize task performance while minimizing energy usage. Active sensing seeks to maximize the efficiency of an estimation task by actively controlling the sensing parameters. Of particular interest for mobile robot teams is the case where active sensing is used for determining the locations at which the robots should move to in order to acquire the most informative measurements. By determining the optimal sensing locations that minimize the estimation uncertainty, active sensing enables a robot team to achieve the desired level of accuracy faster and more efficiently as compared to a random sensing strategy. In this dissertation, we investigate active sensing algorithms for the problems of (i) leader-follower formation control, which is referred to as “active formation control”; and (ii) target tracking, which is termed as “active target tracking”. Furthermore, since precise robot localization is a prerequisite for optimal active sensing, we next focus on reducing the complexity of cooperative localization. The first part of this thesis investigates the problem of active formation control, where our objective is to determine the optimal trajectory for a robot in a leader-follower formation that minimizes its localization uncertainty. In particular, maintaining a perfect formation has been shown to increase the localization uncertainty (as compared to moving randomly), or even to lead to loss of observability when only bearing measurements are available and the robots move on parallel straight lines. To address this issue, we allow the follower to slightly deviate from its desired formation-imposed position and seek to find the next best location where it should move to in order to minimize the uncertainty about its relative pose (position and orientation) estimate, with respect to the leader. Our main contribution is that we formulate and analytically compute the global optimum for this constrained non-convex optimization problem. The second part of this thesis focuses on active target tracking, where our objective is to select the best sensing locations of tracking robots so as to maximize the target-position-estimates’ accuracy. More specifically, we introduce an algorithm that analytically computes the global optimal solution of the one-step-ahead (that is, determining the sensing location at the next time step) single-robot active target tracking problem. Furthermore, we show that the problem of one-step-ahead multi-robot active target tracking is NP-Hard. We then relax the original NP-Hard problem and propose a cyclic coordinate descent algorithm (also called nonlinear Gauss-Seidel relaxation), for determining the next sensing location for each robot, whose computational requirements scale only linearly in the number of robots. Finally, we investigate the problem of multi-step-ahead (that is, generating a sequence of optimal sensing locations over a finite time horizon) single-robot active target tracking, and introduce an efficient algorithm based on the nonlinear Gauss-Seidel relaxation, whose computational complexity is quadratic in the number of time steps considered. The final part of this thesis focuses on reducing the computational complexity of multi-robot cooperative localization. In particular, we aim at reducing the processing requirements of the covariance update step when employing the extended Kalman filter (EKF). In contrast to the standard EKF, whose time complexity is quartic in the number of robots, we introduce an efficient algorithm, named the Modified Householder QR, which exploits the special sparse structure of the measurement (Jacobian) matrix, to reduce the processing cost to cubic. In summary, by introducing active sensing algorithms for efficiently solving important problems that arise in robotics (leader-follower formation control, target tracking), and by reducing the computational complexity of cooperative localization, the research presented in this dissertation aims at optimizing resource utilization while minimizing the operational cost of mobile robots deployed in challenging real-world applications.