Anytime Planning via Function Approximation and Importance Sampling

Motion planning for nonlinear robotic systems is computationally intractable in general (PSPACE-hard), so approximate schemes — discretization-based (A*) and sampling-based (RRT*) — dominate practice. We explore a third approach: function approximation, which transforms planning in the state space into planning in a low-dimensional parameter space of policy function approximators.

Sampled Dubins-car trajectories converging to the optimal policy — Importance sampling for a Dubins-car robot reaching a goal while avoiding obstacles (red). Trajectories shade from light (first sample) to dark (converged).

We use importance sampling to search efficiently for the optimal feedback policy. The algorithm supports parallel computation and anytime planning, making it a natural fit for cloud robotics and GPU-accelerated planning.

Outcomes

Li, L., & Fu, J. (2017). Sampling-based approximate optimal temporal logic planning. 2017 IEEE International Conference on Robotics and Automation (ICRA), 1328–1335. https://doi.org/10.1109/ICRA.2017.7989157