Information-theoretic path planning and navigation

Pedram, Ali Reza
Journal Title
Journal ISSN
Volume Title

Thanks to the wide availability of low-cost and high-performance sensing devices, obtaining a large amount of sensor data has become easier for robots in many applications. Nevertheless, operating a sensor at full capacity may not be the best strategy for resource-constrained robots, especially if it drains the robot’s scarce power or computational resources with little benefit. As sensor modalities increase, how to achieve a given task with minimum perceptual resources (e.g., with reduced sensing frequencies or sensor gains) becomes an increasingly relevant question. Specially in navigation tasks, it is crucial for autonomous agents to find the path plans which require low perception to be followed. This dissertation proposes a two-stage paradigm to reduce the perception cost in autonomous navigation. In the first stage, referred to as the offline path planning stage, a reference path plan requiring moderate navigation perception is sought in uncertain configuration space (the product space of mean and covariance). In the second stage, the online path following stage, the sensor modalities and closed-loop controller are deployed to closely follow the reference path. In the first phase, we introduce a novel path length function accounting for both travel and the expected perception costs. The continuity of the path length function with respect to the topology of the total variation metric is shown. We formulate the path planning problem as a shortest path problem with respect to the introduced cost conditioned by a collision avoidance constraint. We present sampling-based planning algorithms to solve the formulated shortest path problem and propose several improvements to increase their computational efficiency. Leveraging the continuity of the path length, we prove the proposed algorithms find the optimal path almost surely (with probability one) in the limit of a large number of samples. The first phase ends with a smoothing algorithm developed to eliminate the sharp turns in the paths sought by the sampling-based algorithms. For path smoothing, we devise novel collision avoidance constraints that guarantee safety in continuous-time (in transition between states). This dissertation formulates the path following stage as a joint control-sensing problem and develops an attention mechanism to follow the reference path with minimum perception cost (required bits of information). Several numerical simulations are provided to showcase the utility of the proposed algorithms and paradigm in reducing the perception costs, like the frequency of sensor measurements or the number of sensors that must be used simultaneously in navigation.