Apparatus, Method, and Recording Medium for Extended BSA Coverage Path Planning

BSA Path Planning for Extended Cleaning Routes via Landmark Identification and Map Decomposition

This technology optimizes the pathfinding complexity of the conventional Backtracking Spiral Algorithm (BSA) by applying a landmark-based map reduction and decomposition mechanism for path generation in unknown environments.

When applying grid-based BSA algorithms in large-scale map environments, computational complexity increases in proportion to the map size, and the expansion of the path search space leads to delays in generating efficient coverage paths.

This technology introduces a preprocessing step that decomposes or reduces the map based on the presence of convex landmarks after detecting landmarks and classifying them as convex or concave, thereby efficiently managing the path search space by performing BSA on smaller, decomposed map units.

‍

‍

Key Features:

• A step of collecting landmark information by detecting landmarks while moving along the walls of the map.
• A step of determining whether the detected landmarks are convex or concave using the collected information.
• A step of performing either map reduction or map decomposition based on the presence of convex landmarks among the detected landmarks.
• A step of generating a cleaning path using the BSA technique for the decomposed map according to the performed operation.

‍