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.
References
2014.
2. Allen J.F. Maintaining knowledge about temporal intervals, Communications of the ACM.
– 1983. – Vol. 21 (11). – P. 832-843.
3. Allen J. Planning as temporal reasoning, In Proc. Intl. Conf. on Principles of Knowledge Representation
and Reasoning (KR). San Mateo: Morgan Kaufmann, 1991, pp. 3-14,
4. McDermott D. A temporal logic for reasoning about processes and plans, Cognitive Science,
1982, Vol. 6, pp. 101-155.
5. Fisher M., Gabbay Dov M., and Vila L. Handbook of Temporal Reasoning in Artificial Intelligence,
Vol. 1, Elsevier, 2005.
6. Ghallab M., Nau D.S., and Traverso P. Automated Planning: Theory and Practice. The Morgan
Kaufmann Series in Artificial Intelligence, Morgan Kaufmann, Amsterdam, 2004.
7. Bartak R., Morris R., and Venable B. An Introduction to Constraint-Based Temporal Reasoning.
Morgan&Claypool, 2014.
8. Dechter R., Meiri I., and Pearl J. Temporal constraint networks, Artificial Intelligence, 1991,
Vol. 49, pp. 61-95.
9. Ghallab M., Nau D., Traverso P. Automated Planning and Acting. Cambridge University
Press, 2016.
10. Fortin J., Dubois D., Fargier H. Gradual Numbers and Their Application to Fuzzy Interval
Analysis, IEEE Transactions on Fuzzy Systems, 2008, Vol. 16 (2), pp. 388-402.
11. Dubois D., Kerre E., Mesiar R., Prade H. Fuzzy Interval Analysis, In: Dubois D., Prade H.,
Eds., Fundamentals of Fuzzy Sets, pp. 483-581, The Handbooks of Fuzzy Sets Series, Vol. 7.
Springer, 2000
12. Knyazeva M., Bozhenyuk A., Kaymak U. Fuzzy Temporal Graphs and Sequence Modelling in
Scheduling Problem, Communications in Computer and Information Science, 2020, Vol. 1239,
pp. 539-550.
13. Kacprzyk J., Knyazeva M., Bozhenyuk A. Fuzzy Interval-Valued Temporal Automated Planning
and Scheduling Problem, Lecture Notes in Networks and Systems (LNNS), 2021,
Vol. 362, pp. 51-58.
14. Knyazeva M., Bozhenyuk A., Bozheniuk V. Unfolding Fuzzy Temporal Computational Graph
for Project Scheduling Problem, Lecture Notes in Networks and Systems (LNNS), 2021,
Vol.307, pp. 615-622.
15. Sipser M. Introduction to the Theory of Computation. Cengage Learning, 2012.
16. Zeilberger D. Enumeration Schemes and, more importantly, their automatic generation, Annals
of Combinatorics, 1998, 2, pp. 185-195.
17. Patterson J.H., Talbot F.B., Slowinski R., Wegłarz J. Computational experience with a backtracking
algorithm for solving a general class of precedence and resource-constrained scheduling
problems, European Journal of Operational Research, 1990, Vol. 49, Issue 1, pp. 68-79.
18. Hartmann S. Project Scheduling under Limited Resources, Models, Methods, and Applications,
Lecture Notes in Economics and Mathematical Systems, 1999, Vol. 478.
19. Cheng J., Fowler J., Kempf K., Mason S. Multi-mode resource-constrained project scheduling
problems with non-preemptive activity splitting, Computers &Operations Research, 2015,
Vol. 53, pp. 275-287.
20. Reyck B.D., Herroelen W. The multi-mode resource-constrained project scheduling problem
with generalized precedence relations, European Journal of Operational Research, 1999,
Vol. 119, pp. 538-556.
