סמינר: Graduate Seminar
Deterministic Kinodynamic Motion Planning: Theoretical Bounds and Practical Considerations
Date:
March,12,2026
Start Time:
15:00 - 16:00
Location:
506, Zisapel Building
Zoom:
Zoom link
Add to:
Lecturer:
Ido Jacobi
Research Areas:
| Time and safety-critical missions (e.g., search and rescue, inspection planning, autonomous driving, and racing) require robots to perform at the edge of their capabilities. To achieve this level of performance, efficient algorithms are necessary to compute high-quality robot paths while accounting for the robot’s nonlinear dynamic constraints, a problem known as kinodynamic motion planning (KMP). A popular approach to KMP is sampling-based planning, in which the robot’s state space is explored by constructing a search tree that is incrementally expanded via random propagation of sampled robot actions. Unfortunately, such planners offer weak asymptotic guarantees with respect to completeness and optimality, which provide little insight for practitioners. In this work, we advocate for a deterministic approach wherein the constructed search tree is expanded by applying a fixed set of action primitives, while the tree expansion is guided by A*-based rationale using an admissible heuristic. We prove that such a primitive-based planning (PBP) approach, enjoys several theoretical benefits compared to random sampling-based planning: (i) termination in finite time (even if no solution is available); (ii) the first solution found is the optimum within the entire search tree, i.e., further expanding the search tree will not improve solution quality; (iii) a resolution, which determines the maximal distance between the nearest neighbor of each action in the primitive set, can be tuned to achieve a desired solution quality while limiting the size of the search tree. The latter result generalizes and strengthens the work of Fu et al. (2023), which focused on a specific surgical needle system and provided no explicit bounds for the sufficient resolution. Empirically, we evaluate the practical behavior of the PBP approach and demonstrate that it outperforms SST—a popular (randomized) sampling-based approach—on a second-order car model.M.Sc. student under the supervision of Prof. Kiril Solovey.
|