Cleaning robot and shortest path planning method based on cleaning robot

A shortest path planning method based on a cleaning robot, comprising the following steps:

• controlling the cleaning robot to perform cleaning in an area according to a boustrophedon type path, to form a plurality of cleaning lines;
• recording association information of midpoints of at least a part of the cleaning lines to form a node skeleton tree in which the midpoints are represented by nodes, wherein the association information of each of the midpoints includes:
• position information of a node corresponding to the midpoint, position information of a parent node, and information of a number of child nodes of the parent node;
• and
• compressing the node skeleton tree in a process of traversing upwardly from a current node in the node skeleton tree or in a process of traversing upwardly from both the current node and a target node in the node skeleton tree, so as to determine a shortest planned path from the current node to the target node,
• wherein when the cleaning robot moves from a cleaned area to an uncleaned area, association information of a midpoint of an open boundary line between the cleaned area and the uncleaned area is recorded to serve as a node of the node skeleton tree.