Computing a Minimal Set of tSpanning Motion Primitives for Lattice Planners In this paper we consider the problem of computing an optimal set of motion primitives for a lattice planner. The objective we consider is to compute a minimal set of motion primitives that tspan a configuration space lattice. A set of motion primitives tspan a lattice if, given a real number t greater or equal to one, any configuration in the lattice can be reached via a sequence of motion primitives whose cost is no more than t times the cost of the optimal path to that configuration. Determining the smallest set of txe2x80x93spanning motion primitives allows for quick traversal of a state lattice in the context of robotic motion planning, while maintaining a txe2x80x93factor adherence to the theoretically optimal path. While several heuristics exist to determine a txe2x80x93spanning set of motion primitives, these are presented without guarantees on the size of the set relative to optimal. This paper provides a proof that the minimal txe2x80x93spanning control set problem for a lattice defined over an arbitrary robot configuration space is NPcomplete, and presents a compact mixed integer linear programming formulation to compute an optimal tspanner. We show that solutions obtained by the mixed integer linear program have significantly fewer motion primitives than state of the art heuristic algorithms, and out perform a set of standard primitives used in robotic path planning.

Improved Optimization of Motion Primitives for Motion Planning in State Lattices In this paper, we propose a framework for generating motion primitives for latticebased motion planners automatically. Given a family of systems, the user only needs to specify which principle types of motions, which are here denoted maneuvers, that are relevant for the considered system family. Based on the selected maneuver types and a selected system instance, the algorithm not only automatically optimizes the motions connecting predefined boundary conditions, but also simultaneously optimizes the endpoint boundary conditions as well. This significantly reduces the time consuming part of manually specifying all boundary value problems that should be solved, and no exhaustive search to generate feasible motions is required. In addition to handling static a priori known system parameters, the framework also allows for fast automatic reoptimization of motion primitives if the system parameters change while the system is in use, e.g, if the load significantly changes or a trailer with a new geometry is picked up by an autonomous truck. We also show in several numerical examples that the framework can enhance the performance of the motion planner in terms of total cost for the produced solution.