УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Давыдов А.А., Царев Ф.Н., Соколов Д.О. Построение автоматов управления системами со сложным поведением с помощью генетического программирования

Цель исследования: Целью исследования является разработка методов генетического программирования для построения управляющих автоматов и их апробация на практических задачах. Эти методы позволят минимизировать влияние человеческого фактора в разработке систем управления, что уменьшает вероятность ошибок и сокращает время разработки. Апробация будет проводиться на задаче об «Умном муравье» и задаче построения системы управления моделью беспилотного летательного аппарата.

Описание проблемы: Парадигма автоматного программирования была предложена А. А. Шалыто в 1991 году. При использовании этой парадигмы программы проектируются так же, как производится автоматизация технологических процессов: выделяются поставщики событий, объекты управления и система управления. Эта система строится в виде совокупности взаимодействующих конечных автоматов.

Существует ряд задач, в которых построение управляющих автоматов вручную очень трудоемко или невозможно. Поэтому может быть поставлена задача об автоматизации этого процесса.

Краткая аннотация исследования: Для решения задачи автоматизированного построения управляющих конечных автоматов авторы предлагают применять генетического программирования. Этот метод связан с перебором большого числа вариантов. Однако он значительно эффективнее полного перебора – в некоторых задачах достигается ускорение до 1010 раз.

По сравнению с инструментальными средствами, обеспечивающими ручное проектирование конечных автоматов, управляющих системами со сложным поведением, разрабатываемые методы позволят достичь значительно большего уровня автоматизации этого процесса. При этом хорошая структурированность конечных автоматов, достигаемая за счет применения концепции состояния, дает надежду на то, что построенные автоматически конечные автоматы могут быть в дальнейшем модифицированы вручную.

Научная новизна: Прямые мировые аналоги разрабатываемой технологии применения генетического программирования для построения конечных автоматов, управляющих системами со сложным поведением, отсутствуют. Решение, наиболее близкое к предлагаемому, описано в книге Фогель Л., Оуэнс А., Уолш М. «Искусственный интеллект и эволюционное моделирование»: М.: Мир, 1969. Однако автоматы, порождаемые по методике, излагаемой в этой книге, относятся только к классу предсказателей.

Эта методика не может быть использована для построения автоматов, управляющих системами со сложным поведением, так как ориентирована на построение автоматов, имеющих небольшое количество вариантов комбинаций входных переменных, и использование сравнительно простого метода представления автоматов. Для рассматриваемого класса задач автоматы следует представлять более сложными структурами, так как число входных переменных может быть достаточно большим.