МЕТОД И АЛГОРИТМ ПЛАНИРОВАНИЯ ОПЕРАЦИЙ НА ОСНОВЕ МОДЕЛИ НЕЧЕТКОГО КОНЕЧНОГО АВТОМАТА
Аннотация
Рассматривается задача планирования, как важная оптимизационная задача, стоя-
щая перед многими транспортными и роботизированными приложениями. Для решения
задач планирования подходы основаны на методах оптимизации, методах выборки и дис-
кретизации (sampling-based methods), и обычно такого рода задачи являются NP-
трудными и многомерными. В данной статье разработан метод планирования и состав-
ления расписаний на основе нечеткой модели конечного автомата. Дано нечеткое графо-
вое представление задачи составления расписания и планирования операций. В работе при-
ведены два подхода к формальной постановке задачи планирования с ограниченными ресур-
сами и временными переменными: ориентированный на состояния (с переходами между
состояниями), ориентированный на темпоральное упорядочивание (на временной шкале).
Темпоральное моделирование для задач планирования подразумевает качественный подход
к управлению распределением операций или топологическим упорядочением, а также коли-
чественный подход к обработке неточных длительностей, взаимосвязей между операция-
ми по многочисленным параметрам. Введены понятия нечетких интервалов и нечетких
отношений для планирования операций на графе. Разработан алгоритм планирования, ос-
нованный на основе теории автоматов и темпоральном моделировании в условиях неопре-
деленности. Используя формализм теории автоматов, проблема планирования и нахожде-
ния оптимальных путей решается путем последовательного изменения и анализа состоя-
ний планируемой системы с использованием различных операций, пока не будет найдено
решение. В работе обсуждается идея упорядоченного во времени частичного расписания,
связанного с каждым состоянием планируемой системы. Предложена модель конечного
автомата для системы планирования в условиях неопределенности. Разработан метод и
алгоритм планирования операций на основе недетерминированного конечного автомата и
схемы перечислений. Недетерминированные вычисления для задачи планирования пред-
ставляют собой дерево решения, корень которого соответствует началу процесса плани-
рования, а каждая точка ветвления в дереве соответствует точке вычисления, в которой
у машины есть несколько вариантов выбора.
Литература
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.