METHOD AND ALGORITHM FOR OPERATION PLANNING BASED ON FUZZY FINITE AUTOMATA MODEL

Abstract

In this paper the planning and scheduling problem as an important optimization problem in
many transportation and robotic applications is discussed. To solve planning problems, the main
approaches are based on optimization methods, sampling-based methods, and usually such kinds
of problems are NP-hard and high dimensional. In this work, the method for planning and scheduling
based on the fuzzy finite state machine model is developed. Fuzzy graph presentation of the
scheduling problem and operation planning is given. The paper presents two approaches to the
formulation of the planning problem with limited resources and temporal variables: state-oriented
(with transitions between states), temporal ordering-oriented (on a time scale). Temporal modeling
for planning problems implies a qualitative approach to managing the distribution of operations
or topological ordering, as well as a quantitative approach to handling imprecise durationsrelationships between operations in multiple parameters. The concepts of fuzzy intervals and fuzzy
relations are introduced for planning operations on a graph. A planning algorithm based on the
theory of automata and temporal modeling under uncertainty has been developed. Using this formalism,
a path planning problem is solved by successively altering a state using various operations
until a solution is found. The idea of temporal-ordered partial schedule associated with the
planning state of the system is discussed. A model of a finite automaton for a planning system under
conditions of uncertainty is proposed. A method and algorithm for scheduling operations
based on a non-deterministic finite automaton and an enumeration scheme have been developed.
The non-deterministic computation for a scheduling problem is a decision tree whose root corresponds
to the beginning of the scheduling process, and each branch point in the tree corresponds
to a computation point at which the machine has multiple choices. And the finite state machine
model (automata) for the planning system under uncertainty is suggested.