Sampling-based Optimized Adaptive Discretization and its Applications in Robotics

Discretization is critical in robotics because real robotic systems operate in continuous, high-dimensional state spaces that are intractable for most computational methods. Converting these continuous spaces into compact finite representations enables efficient planning, learning, and safety analysis. However, existing discretization methods often prioritize approximation accuracy while neglecting explicit control of partition size. This imbalance causes state representations to grow exponentially with dimension, which limits the scalability of downstream robotic applications.

This thesis presents a principled framework for optimal discretization that explicitly balances accuracy and representation complexity. Building upon theoretical conditions that characterize an optimal partition structure, we introduce two sampling-based adaptive discretization algorithms: GOAD and λ-OAD. GOAD maximizes split gain to better approximate the optimal solution with highly compact partitions, while λ-OAD enforces a dynamically adapting split-gain threshold that balances accuracy with reduced computational cost.

Extensive experiments across a variety of synthetic datasets and robotic tasks demonstrate the effectiveness of the proposed methods compared to state-of-the-art discretization techniques. Both GOAD and λ-OAD achieve substantially fewer partitions under the same approximation accuracy, and λ-OAD further improves efficiency by significantly reducing computation time. These results highlight the scalability and practical advantages of the proposed methods for robotics applications requiring accurate yet computationally efficient discretization.

Committee: Bowen Weng (major professor), Yang Li, Xiaoqiu Huang, and Yan-Bin Jia