運用改良式A*演算法於智慧型掃地機器人全覆蓋型路徑規劃研究與開發

The development of this project is oriented to include three major themes applied to robot vacuum cleaner, including a point-to-point path planning algorithm, a region segmentation algorithm and a real-time guidance mechanism algorithm. The point-to-point path planning is improved by the A* search algorithm. It has the characteristics of being able to plan the best path, and the implementation of a two-stage soft and hard protection strategy with edge detection can effectively avoid robots and walls or obstacles. In addition, using the integrated data structure of Heap and Matrix can reduce the number of calculations required for search and reduce the time spent on path planning.The segmentation activity space algorithm uses image morphologies such as erosion and growth algorithms to find the center point of the area and divide it into independent blocks. Therefore, the robot can only clean a part of the area or avoid the problem of task interruption problem from running out of electricity or detergent.The real-time guidance mechanism algorithm in a dynamic environment is a supporting measure for the robot to perceive that it cannot go to the destination along the predetermined path. This algorithm designs a utility value evaluation mechanism to reflect the map changes, and then calculates the ability to guide the robot according to the robot’s behavioral ability. The direction to go to the end and avoid obstacles. The application of three sets of subsystems to autonomous sweeping robots can improve its operational capabilities.