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.