МЕТОД И АЛГОРИТМ ПЛАНИРОВАНИЯ ОПЕРАЦИЙ НА ОСНОВЕ МОДЕЛИ НЕЧЕТКОГО КОНЕЧНОГО АВТОМАТА

Аннотация

Рассматривается задача планирования, как важная оптимизационная задача, стоя- щая перед многими транспортными и роботизированными приложениями. Для решения задач планирования подходы основаны на методах оптимизации, методах выборки и дис- кретизации (sampling-based methods), и обычно такого рода задачи являются NP- трудными и многомерными. В данной статье разработан метод планирования и состав- ления расписаний на основе нечеткой модели конечного автомата. Дано нечеткое графо- вое представление задачи составления расписания и планирования операций. В работе при- ведены два подхода к формальной постановке задачи планирования с ограниченными ресур- сами и временными переменными: ориентированный на состояния (с переходами между состояниями), ориентированный на темпоральное упорядочивание (на временной шкале). Темпоральное моделирование для задач планирования подразумевает качественный подход к управлению распределением операций или топологическим упорядочением, а также коли- чественный подход к обработке неточных длительностей, взаимосвязей между операция- ми по многочисленным параметрам. Введены понятия нечетких интервалов и нечетких отношений для планирования операций на графе. Разработан алгоритм планирования, ос- нованный на основе теории автоматов и темпоральном моделировании в условиях неопре- деленности. Используя формализм теории автоматов, проблема планирования и нахожде- ния оптимальных путей решается путем последовательного изменения и анализа состоя- ний планируемой системы с использованием различных операций, пока не будет найдено решение. В работе обсуждается идея упорядоченного во времени частичного расписания, связанного с каждым состоянием планируемой системы. Предложена модель конечного автомата для системы планирования в условиях неопределенности. Разработан метод и алгоритм планирования операций на основе недетерминированного конечного автомата и схемы перечислений. Недетерминированные вычисления для задачи планирования пред- ставляют собой дерево решения, корень которого соответствует началу процесса плани- рования, а каждая точка ветвления в дереве соответствует точке вычисления, в которой у машины есть несколько вариантов выбора.