A generalization of Bellman's equation with application to path planning, obstacle avoidance and invariant set estimation. (May 2021)

• Record Type: Journal Article
• Authors: Jones, Morgan; Peet, Matthew M.
• Is Part Of: Automatica. Volume 127(2021)
• Publication Date: 2021-05
• Subjects: Dynamic programming -- Path planning -- Maximal invariant sets -- GPU-accelerated computing; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2021.109510
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: The standard Dynamic Programming (DP) formulation can be used to solve Multi-Stage Optimization Problems (MSOP's) with additively separable objective functions. In this paper we consider a larger class of MSOP's with monotonically backward separable objective functions; additively separable functions being a special case of monotonically backward separable functions. We propose a necessary and sufficient condition, utilizing a generalization of Bellman's equation, for a solution of a MSOP, with a monotonically backward separable cost function, to be optimal. Moreover, we show that this proposed condition can be used to efficiently compute optimal solutions for two important MSOP's; the optimal path for Dubin's car with obstacle avoidance, and the maximal invariant set for discrete time systems.