Dozens of excavations, and the order matters
Building a berm is not one excavation, it is dozens, and the order matters. Every pass changes the terrain the next one starts from, and driving between distant excavation and deposition sites is the dominant cost on a rover with a fixed power budget. The space of orderings is combinatorial, so uninformed search does not finish.
Two levels of search
- A bilevel formulation. The upper level searches over which excavation zone to dig, which berm section to deposit into, and in what order; the lower level plans the actual drive between any two of those poses, and hands its cost back up as the edge weight.
- Since energy spent is proportional to distance traveled for an electric rover at steady speed, where drive force is dominated by rolling resistance, this turns an energy objective into a distance objective the search can optimize directly.
- Used a hybrid A* planner for the lower level, so every transition is a path the rover can actually drive over traversable terrain rather than a straight-line estimate.
- Built the heuristic by relaxing the problem to a collision-free TSP over deposition poses and solving it with Google OR-Tools.
- Ran weighted A* at several inflation factors to trade optimality against search time.
- Implemented in C++ on ROS 2 as a task optimizer node, with worksites specified in YAML and the resulting sequence rendered as an animation for inspection.
The TSP relaxation is what makes the search finish at all. On the hardest of three worksites, uninformed search returned no plan in ten minutes, while the heuristic solved it in 70 seconds. Inflating to eps=5 cut that to 27 seconds for 1.3 percent more plan cost, 174.6 against 172.3.
Why the relaxation is the result
- The TSP relaxation is the whole result. It is cheap to compute and tight enough that it turns an intractable search into one that finishes, which is the difference between the planner existing and not.
- Weighted A* was a very good trade here. A 2.6x speedup for a 1.3 percent worse plan is worth taking on a rover where planning time is idle time.
- Computing edge costs with hybrid A* rather than Euclidean distance meant the plan did not fall apart when handed to the controller.