Autonomous exploration method and computing device performing the same

Autonomous Exploration Robot Selecting Optimal Frontier Points via Frontier Filtering and Parallel Path Planning

This technology is an autonomous exploration method and computing device that allows a mobile robot to represent an unexplored space using an occupancy grid map, extract candidate frontier points using an FFP frontier detection algorithm, and autonomously determine and move to the nearest target. It filters out useless candidates using obstacle and frontier filters, and determines the next destination by calculating paths to the remaining candidates in parallel.

Existing grid map-based exploration methods suffer from excessive time consumption for frontier detection and path calculation as map data grows. While topology maps offer better memory efficiency, they lack precision, making it difficult to determine exact positions within nodes or navigate with high accuracy.

This technology reduces computational load by downsampling the occupancy grid map scanned from the robot's starting position. It removes "spurious points"—inaccessible locations where the obstacle probability (cost map score) of patches around frontier points exceeds a threshold or where the frontier metric calculated by the ratio of unknown cells is low. Subsequently, it uses multiple threads with branching and boundary conditions to simultaneously explore paths to each frontier point, selecting the one with the shortest path as the optimal frontier point and marking the exploration trajectory on the map. Applicable to disaster search robots, warehouse mapping robots, and indoor cleaning or patrol robots, this allows robots deployed without prior maps to complete a full map of a space in a short time without getting stuck in dead-end false frontiers.

‍

‍

Key Features:

• Generating an occupancy grid map for a target space containing unknown areas
• Extracting a plurality of frontier points for exploring unknown areas on the occupancy grid map using a frontier detection algorithm
• Removing spurious points, which are false frontier points including inaccessible points, from the extracted frontier points
• Determining the optimal frontier point with the shortest path by simultaneously exploring movement paths from the mobile robot's current position to each frontier point using a parallel path algorithm

‍

This invention was developed with the support of the Ministry of Science and ICT through research and human resource development for core technologies for Simulated Reality content implementation.

‍