Prioritized Robotic Exploration with Dynamic Deadlines

Autonomous exploration using mobile robots, commonly referred to as robotic exploration, entails simultaneously performing robot perception, localization, and motion planning to explore an unknown environment. Most prior indoor robotic exploration algorithms focus on exploring the entire environment. We consider exploration under deadlines dynamically imposed either by the robot’s battery or by the environment. Such time-sensitive robotic exploration is critical in dangerous environments as it provides vital initial information about the geometric structure and layout of the environment for subsequent operations. For instance, firefighters can utilize an initial map generated by this deadline constrained robotic exploration to rapidly navigate a building on fire. In the presence of deadlines, the robots should identify the semantically significant regions of the environment (e.g., corridors) and prioritize those that enable them to determine the environment's geometric structure and return to the starting position before the deadline.
This dissertation addresses the problem of autonomous exploration in indoor environments with dynamic deadlines. The problem is NP-hard and requires exponential time to solve optimally. Therefore, we present a short-horizon exploration algorithm, the priority-based greedy exploration algorithm, and several long-horizon exploration algorithms; these include adaptations of the orienteering problem and the profitable tour problem for single-robot and multi-robot exploration of unknown environments with dynamic deadlines. Furthermore, we present a test suite of environments and exploration metrics to benchmark the real-world efficiency of exploration algorithms in office-like environments. Our single-robot experiments reveal that the priority-based greedy exploration algorithm, which focuses on exploring semantic regions with higher connectivity, consistently outperforms the baseline cost-based greedy exploration algorithm in terms of environment layout identification and exploration efficiency. Moreover, the priority-based greedy algorithm was found to be on par with the computationally expensive long-horizon exploration algorithms in terms of percent of the area explored within the deadline. Long-horizon exploration algorithms on the other hand exhibit consistent performance with low variance over repeated experiments. Moreover, the multi-robot priority-based greedy exploration algorithm demonstrated better performance compared to the multi-robot baseline exploration algorithm and performed on par with the multi-robot long-horizon based exploration algorithm while being computationally faster.