  Search-based planning with motion primitives is a powerful motion planning
technique that can provide dynamic feasibility, optimality, and real-time
computation times on size, weight, and power-constrained platforms in
unstructured environments. However, optimal design of the motion planning
graph, while crucial to the performance of the planner, has not been a main
focus of prior work. This paper proposes to address this by introducing a
method of choosing vertices and edges in a motion primitive graph that is
grounded in sampling theory and leads to theoretical guarantees on planner
completeness. By minimizing dispersion of the graph vertices in the metric
space induced by trajectory cost, we optimally cover the space of feasible
trajectories with our motion primitive graph. In comparison with baseline
motion primitives defined by uniform input space sampling, our motion primitive
graphs have lower dispersion, find a plan with fewer iterations of the graph
search, and have only one parameter to tune.
