Research on BCD Algorithm Based on Boundary Vector Statistical Map Alignment
摘要
Mobile robot full coverage path planning has broad prospects in fields such as indoor cleaning, military operations, and agricultural cultivation and harvesting. However, when the initial pose coordinate system of the mobile robot for mapping is not aligned with the boundaries of the indoor environment—meaning that there is an angle between the map coordinate system and the wall boundaries—numerous issues arise during the subsequent full coverage path planning process. The full coverage algorithm based on the BCD algorithm (The Boustrophedon Cellular Decomposition algorithm) employs the Hough transform to detect lines for deviation detection and map alignment. However, it suffers from problems such as algorithm complexity, low computational efficiency, and high power consumption, making it unsuitable for low computational power and low power consumption requirements in practical applications. This paper proposes a lightweight and high-precision boundary rectangular coordinate system detection method based on map boundary extraction, building upon the BCD algorithm. By extracting the map boundaries, we can determine the overall shape of the map. Subsequently, key vectors formed by the combination of key points on the boundaries and their parallel or orthogonal relationships are used to identify the vertical boundary of the map walls and establish the wall coordinate system. This system is then rotated to align with the world coordinate system based on the angle between them, thus achieving map alignment and providing a rational map for subsequent path planning. Tests on various simulated and real maps with deviations demonstrate that this algorithm can accurately identify the angle between the coordinate system of the map's right-angled walls and the world coordinate system, successfully achieving map alignment. Finally, verify the full coverage path planning effect on the rotated and aligned map.