A high-speed method for computing reachable sets based on variable-size grid

Abstract

In this paper, we improve the dynamic programming based reachable set computation method by replacing the constant size grid in the original method with a variable size grid. With this improvement, the computational time consumption can be significantly reduced while maintaining the accuracy. The proposed method represents the reachable set as a sublevel set of a discount cost-to-go function, which is generated by dynamic programming. In order to compute the discount cost-to-go function quickly and accurately, the proposed method consists of three steps: (1) Rough computation. This step uses a coarse grid to obtain an interpolation function that is close to the real discount cost-to-go function; (2) Upsampling. This step is for generating a fine grid; (3) Fine tuning. This step generates an interpolation function that exactly approximates the real discount cost-to-go function. This paper theoretically proves the correctness of the proposed method and verifies its effectiveness by some examples.

Keywords: Dynamic programming; Function approximation; Grid size; Reachable set.