Prioritized Robotic Exploration with Deadlines: A Comparison of Greedy, Orienteering, and Profitable Tour Approaches

This paper addresses the problem of robotic explo- ration of unknown indoor environments with deadlines. Indoor exploration using mobile robots has typically focused on ex- ploring the entire environment without considering deadlines. The objective of the prioritized exploration in this paper is to rapidly compute the geometric layout of an initially unknown environment by exploring key regions of the environment and returning to the home location within a deadline. This pri- oritized exploration is useful for time-critical and dangerous environments where rapid robot exploration can provide vital information for subsequent operations. For example, firefighters, for whom time is of the essence, can utilize the map generated by this robotic exploration to navigate a building on fire. In our previous work, we showed that a priority-based greedy algorithm can outperform a cost-based greedy algorithm for exploration under deadlines. This paper models the prioritized exploration problem as an Orienteering Problem (OP) and a Profitable Tour Problem (PTP) in an attempt to generate exploration strategies that can explore a greater percentage of the environment in a given amount of time. The paper presents simulation results on multiple graph-based and Gazebo environments. We found that in many cases the priority-based greedy algorithm performs on par or better than the OP and PTP-based algorithms. We analyze the potential reasons for this counterintuitive result. I. INRODUCTION A significant research area in robotics and computer vision is 3D data acquisition and reconstruction to create a map of an initially unknown environment. A challenging problem is to select the locations in the partially observed map that the robot must visit to explore and map the environment further. The speed and extent of exploration by the robot is constrained by its limited knowledge of the environment, and constraints on the available time and energy of the robot. The prioritized exploration problem’s objective is to identify the layout of the environment within a deadline [1]. For example, such a deadline may be imposed by excessive radiation in an environment, where the robot has to explore quickly to avoid long term damage to its hardware, or by a need to return safely despite a rapidly depleting battery. A commonly used technique is to iteratively compute a target position for the robot to visit, in the partially known map. The map is updated as the robot moves to the target position. To explore the environment quickly and efficiently, the robot should ideally visit each target location at most once. In practice, with limited knowledge of the environment, the robot should minimize revisiting locations that it has already visited. This connects our problem to the Hamiltonian Path The authors are with the Department of Computer Science, University of North Carolina at Charlotte, NC 28223, USA. This work was partially supported by NSF Award IIP-1919233. sdatta3@uncc.edu, sakella@uncc.edu Problem and node routing problems such as the Traveling Salesperson Problem (TSP). These well known problems have been used to model coverage problems where each vertex needs to be visited only once [2], [3]. The prioritized exploration problem is a variant of the exploration problem where the robot must explore an initially unknown environment to compute its layout (i.e., connectivity) maximally while returning to the home location within a deadline. It attempts to do so by creating a path that visits high priority regions while ensuring the robot returns to the home location within the deadline. The prioritized exploration problem can be modeled as the problem of visiting a sequence of the most rewarding vertices within the limited exploration time. Vertices with higher rewards provide better views of the unknown environment. This paper considers the following question: Would using a Orienteering Problem (OP) formula- tion or a Profitable Tour Problem (PTP) formulation to explore the environment improve performance? The OP and PTP are NP-complete problems [4] and require time exponential in the number of vertices to solve optimally. In this paper, when needed we reduce the number of candi- date vertices to a feasible size so the prioritized exploration problem can be solved rapidly. The paper discusses the relevant literature in Section II, and describes adaptation of the Orienteering Problem and Profitable Tour Problem for the prioritized exploration problem in Section III. Results of simulation experiments are presented in Section IV, followed by a discussion of the behavior of the exploration algorithms in Section V. II. RELATED WORK The problem of robotic exploration has been studied from multiple perspectives. The work described in this paper builds on previous work on robot exploration, mapping techniques, and path planning. Cost-based frontier exploration techniques that have been used for single-robot exploration [5] and multi-robot explo- ration [6] have laid the groundwork for robotic exploration. Next-best-view [7] approaches such as receding horizon next- best-view [8] have also been used for 3D mapping of envi- ronments. Robotic exploration has been modeled as different problems such as target searching, mapping, and coverage in unknown or partially observed environments [9], [10], [11], [12], [3]. Another approach for robot exploration is Active SLAM, a variant of the Simultaneous Localization and Mapping problem (SLAM). Active SLAM is the task of actively plan- ning robot paths while simultaneously building a map and 2023 IEEE International Conference on Robotics and Automation (ICRA 2023) May 29 - June 2, 2023. London, UK 979-8-3503-2365-8/23/$31.00 ©2023 IEEE 5737