Recomposable restricted finite state machines: definition and solution approaches

ABSTRACT

Many real-world systems operate and make decisions using limited resources in dynamically changing environments, where the changes can be unpredictable. In this paper, the Restricted Finite State Machine is defined, and its optimality studied; it is a composed finite state machine with input restrictions that can handle limited resources. Then, the Recomposable Restricted Finite State Machine is defined, and its optimality investigated; it can handle unpredictably dynamically changing environments, by reacting to environment changes. In general, the local optimal policies do not generate the global optimal policy of the Recomposable Restricted Finite State Machine and global optimality cannot be achieved without knowledge of future. Thus, a heuristic method, Limited Breath First Search, is developed. The numerical simulation results indicate that the heuristic method performs well with proper parameters, and also indicates that local sub-optimal solutions can be better than the local optimal policies for the global policy/solution of Recomposable Restricted Finite State Machines.

KEYWORDS:

• Recomposable restricted finite state machine
• unpredictability
• decision making
• task scheduling
• optimal policy
• heuristics

Acknowledgments

The authors wish to acknowledge the contributions of Professor Pierre T. Kambamba, who passed away September 20, 2014 and cannot be listed as a co-author.

Disclosure statement

No potential conflict of interest was reported by the authors.