Hill climbing algorithm for constructing a lane line map

A tangible, non-transitory, machine-readable medium, comprising machine-readable instructions, that when executed by one or more processors, cause the processors to:

• receive a multi-layer probability density bitmap, wherein the multi-layer probability density bitmap represents a plurality of lane lines of a roadway sensed by a plurality of sensors of a plurality of vehicles, and the multi-layer probability density bitmap includes a plurality of points;
• recursively conduct a hill climbing search using the multi-layer probability density bitmap to create a plurality of lines;
• and
• create a high-definition (HD) map of the roadway using the plurality of lines determined by the hill climbing search;
• receive lane line data from the plurality of sensors;
• create the multi-layer probability density bitmap using the lane line data;
• determine a start point for each of the plurality of points of the multi-layer probability density bitmap;
• determine that a selected point satisfies a first condition, a second condition, and a third condition;
• determine that the selected point is the start point in response to determining that the selected point satisfies the first condition, the second condition, and the third condition, wherein the first condition is that the selected point is a local peak, the second condition is that the selected point has not been analyzed before using the hill climbing search, and the third condition is that a density value of the selected point is greater than a predetermined, minimal density threshold;
• find a plurality of candidate points on a circle drawn around a current exploring point, wherein the selected point is the current exploring point;
• determine whether a selected candidate point is a good candidate point for each of the plurality of candidate points;
• and
• determine that the selected candidate point of the plurality of candidate points is the good candidate point in response to satisfying a first good candidate condition, a second good candidate condition, a third good candidate condition, and a fourth good candidate condition, wherein the first good candidate condition is that a difference between a probability density bitmap value of the current exploring point and a probability density bitmap value of the selected candidate point is less than a predetermined density threshold, the second good candidate condition is that the current exploring point should not have been visited before, the third good candidate condition is that a smoothness value from of a line from the current exploring point to the selected candidate point is less than a predetermined smoothness threshold, and the fourth good candidate condition is that a heading difference is less than a predetermined heading difference threshold, the heading difference is the difference between a first vector and a second vector, the first vector is from the current exploring point to the selected candidate point, and the second vector is from a first node in the line to a second node, and the second node is the current exploring point.