Fast Frontier-Exploration for Unmanned Autonomous Vehicles with Resource Constraints

Unmanned Autonomous Vehicles (UAV) have received wide attention. Their capability to autonomously navigate around the environment enables many applications including search-and-rescue, surveillance, wildlife protection and environment mapping. The key technique to empower such capabilities is the frontier-exploration algorithm, which periodically makes decisions on where the vehicle should explore next in an unknown environment based on previously acquired knowledge. However, such algorithms are computationally expensive. In a practical system, the computation is usually offloaded to a powerful computer, causing a significant delay in the response time. This also makes the system strongly dependent on the presence of a stable wireless connection. These factors prohibit the application of the frontier-exploration algorithm to resource-constrained miniature UAVs with limited battery and computation power.

In this work, we present an algorithm to reduce the computation cost of the state-of-the-art mutual information based frontier-exploration algorithm. The key idea behind the algorithm is to use the same computations between different parts of the mutual information computation and reduce redundant computations. Additionally, our approach seeks a more compact representation of the environment, which minimizes the number of operations required to run the algorithm.

In practice, our algorithm enables the complicated frontier-exploration algorithm to be deployed to a battery-powered miniature UAVs with limited computation power. The algorithm makes it possible for the UAV to explore a closed unknown environment with no stable wireless connections. Thanks to the capability of local computation, the latency of running the algorithm is reduced, enabling the UAVs to explore faster and quickly react to the changes in the environment. The saved computation power can be allocated to the actuators of the UAV, enabling the UAVs to stay in the air longer and therefore explore a larger area given fixed power budget.