記号的2値符号化スキームに基づいた動的計画法の代数計算による効率化

概要

論文の詳細を見る
This paper shows that it is possible to decrease the computational cost of Dynamic Programming methods for problems of planning a certain kind of Stochastic Discrete Event System (SDES), if those methods are constructed based on the modeling method called Symbolic Binary Coding Scheme (SBCS). The considered property of such a system is that the number of following states from an origin state is rather smaller than the number of possible situational-inputs (SIs) which the system suffers. Here, the SI is one of the components involved in a model by the SBCS, and a kind of augmented disturbance. The property raises the conjecture that some SIs may have the same influence to the system, and if so, they can be united to an SI which typifies them. This conjecture can be achieved by algebraically simplifying the state transition function, which is modeled as a set of elementary binary functions by the SBCS, with the aid of Computer Algebra Systems. That unification obviously decreases the computational cost of DP methods. In computer illustrations, the effectiveness of employing that unification is shown through results by applying the Value Iteration method to elevator operation problems of small scale.
2009-07-01