A Markov Decision Problem Approach to Goal Attainment
Candra Meirina, Y.N. Levchuk, Georgiy Levchuk, Krishna Rao Pattipati · IEEE Transactions on Systems Man and Cybernetics - Part A Systems and Humans · 2007
A new Markov decision problem (MDP)-based method for managing goal attainment (GA), which is the process of planning and controlling actions that are related to the achievement of a set of defined goals in the presence of resource and time constraints, is proposed. Specifically, we address the problem as one of optimally selecting a sequence of actions to transform the system and/or its environment from an initial state to a desired state. We begin with a method of explicitly mapping an action-GA graph to an MDP graph and developing a dynamic programming (DP) recursion to solve the MDP problem. For larger problems having exponential complexity with respect to the number of goals, we propose guided search algorithms such as AO*, AOepsiv*, and greedy search techniques, whose search power rests on the efficiency of their heuristic evaluation functions (HEFs). Our contribution in this part stems from the introduction of a new problem-specific HEF to aid the search process. We demonstrate reductions in the computational costs of the proposed techniques through performance comparison with standard DP techniques. We conclude this paper with a method to address situations in which alternative strategies (e.g., second best) are required. The new extended AO* algorithm identifies alternative control sequences for attaining the organizational goals.