Электронный
математический и медико-биологический журнал. - Т. 14. -
Вып. 1. - 2015. - URL:
http://www.smolensk.ru/user/sgma/MMORPH/TITL.HTM
http://www.smolensk.ru/user/sgma/MMORPH/N-45-html/TITL-45.htm
http://www.smolensk.ru/user/sgma/MMORPH/N-45-html/cont.htm
УДК:
004.8
Способы и
программные средства автоматизированной выработки алгоритмов поведения
интеллектуального агента
Ó
2015 г. Сорокин Е. В.
В работе предложены
способы и программные средства автоматизированной выработки алгоритмов
поведения интеллектуального агента с использованием генетического алгоритма для
генерации стратегических решений. Предлагается новый способ представления
алгоритма поведения интеллектуального агента с использованием модели
интерпретации алгоритма на языке макрокоманд робота. Для выработки и оценки алгоритмов
разработана имитационная модель с использованием библиотеки OpenGL в среде программирования Delphi 7.
Ключевые слова: Модель интерпретации кода, модель
интерпретации алгоритма на языке макрокоманд робота, генетический алгоритм.
Современную деятельность человека трудно
представить без использования различных автоматических и автоматизированных
устройств. Такие устройства получают все большее распространение во всех сферах
человеческой деятельности – от бытовой техники до сложных систем управления
производственными процессами. Особенно важную роль занимает разработка роботов,
способных без вмешательства человека решать поставленную задачу, адаптируясь к
окружающей среде. Задача, кажущаяся достаточно непростой имеет много различных
подходов к решению.
Работа посвящена разработке способов и
программных средств, для выработки алгоритмов поведения роботов, решающих
поставленную задачу при различных условиях окружающей среды. В частности, одним
из направлений является решение соревновательных задач, например, задача
определения местоположения заданных объектов за минимальное время в
ограниченном пространстве.
Целью исследования является повышение
качества алгоритмов поведения робота, за счет способов и средств
автоматизированной выработки алгоритмов поведения интеллектуального агента.
В качестве основного инструмента для
автоматизированной выработки алгоритмов используется модель интерпретации
макрокоманд робота, построенной на основе модели интерпретации кода программ.
Модель интерпретации кода (MIC) – это иерархически организованная совокупность
блоков. Блок – структурная единица, представляющая из себя операторные скобки
или одну из базовых конструкций языка программирования без учета операторов, вложенных
в нее. Каждому блоку ставятся в соответствие следующие возможные блоки и
предыдущий блок, из которого мы к нему пришли. В результате, мы получаем последовательность
команд, в которой имеются все необходимые сведения о месте того или иного
оператора и его особенностях [1].
Робот выполняет некоторые действия, в
зависимости от поставленной задачи и внешних факторов окружающей среды. MIC можно представить как отображение некоторого алгоритма
действий робота. Модель
интерпретации макрокоманд робота отличается от классической модели
интерпретации кода программ использованием макрокоманд робота вместо операторов
присвоения. Макрокомандами робота могут выступать различные виды движений вперед,
назад, направо, налево с разными скоростями и временем действия, включение,
выключение приборов освещения, повороты сервоприводов, оценка расстояний
дальномерами и другие действия, которые робот способен выполнить.
Рассмотрим простую задачу: имеется круг
радиусом в 1м, очерченный линией черного цвета, поверхность покрытия дорожного
полотна твердая. Робот располагается в центре круга, произвольным образом
расставляются кегли. Задача робота: сбить кегли за минимальное время, не выходя
за пределы круга. Робот представляет собою четырехколесную полно-приводную
конструкцию с отсутствием поворотного механизма колес. Ширина машины не более 15см, длина не более 25см, масса
0.5кг, колеса прорезиненные.
В основе управления роботом лежит
программно-аппаратная платформа arduino uno rev3.
Модель Arduino Rev3 выполнена
на базе процессора ATmega328p с тактовой частотой 16 МГц,
обладает памятью 32 кб и имеет 20 контролируемых контактов ввода и вывода для
взаимодействия с внешним миром.
Платформа состоит из аппаратной и
программной частей, обе чрезвычайно гибки и просты в использовании. Для
программирования используется упрощённая версия C++, известная так же как Wiring. Разработку можно вести как с использованием
бесплатной среды Arduino IDE, так и с помощью
произвольного C/C++ инструментария. Поддерживаются операционные системы Windows, MacOS X и Linux.
Передача сигнала с платы управления на
колеса идет через специальный драйвер Motor Shield. Motor
Shield — плата расширения для Arduino
на базе чипа L298P, позволяющая управлять моторами с напряжением 7–24 В.
Данные об окружающей среде собираются с
помощью инфракрасного дальномера. Сенсор определяет расстояние по отражённому
лучу света в инфракрасном спектре. Дальномер может использоваться для объезда
препятствий и ориентирования на местности. Напряжение
питания: 5В, потребляемый ток: 33 – 50 мА, диапазон расстояний: 20 – 150см.
Поскольку в основе работы устройства используется свет, сенсор плохо подходит
для определения расстояния до светопоглощающих
объектов.
Выработка стратегии решения задачи
осуществляется в два этапа:
-
этап сбора данных
об окружающей среде;
-
этап
моделирования и формирования стратегии решения.
Этап сбор данных об окружающей среде
позволяет оценить основные параметры, которые могут повлиять на качество
выбранной стратегии: коэффициент трения с дорожным полотном, освещенность и
другие важные параметры. Параметры выработанного алгоритма для движения на
деревянной ровной поверхности в светлое время суток значительно отличаются от
параметров движения по льду на наклонной поверхности. При неправильном
определении окружающей среды поворот на 30 градусов может соответствовать
развороту. Движение с выключенными осветительными приборами будет искажать
показатели дальномеров.
Этап моделирования и формирования
стратегии решения задачи является наиболее сложным и основополагающим в
рассматриваемой работе. Выработка стратегии осуществляется с помощью
генетического алгоритма. Поскольку генетические алгоритмы требуют больших
вычислительных затрат, решение не может быть найдено на платформе arduino, этой задачей занимается программное обеспечение на
ПК, с которым связывается робот. Генетические алгоритмы в общем случае хорошо
поддаются распараллеливанию. При написании параллельной версии можно
использовать так называемую «островную модель» генетических алгоритмов.
Островная модель характеризуется тем, что вся популяция делится на несколько подпопуляций, каждая из которых размещается на своем
процессоре, которые выполняют генетические операции, а результатами
обмениваются посредством миграции. Каждая из этих относительно небольших подпопуляций вычисляется независимо на своем процессоре и
время от времени обменивается особями с другими подпопуляциями.
На каждом острове подпопуляция подвергается в
точности таким же генетическим операциям на таком же генотипе, что и в
последовательном алгоритме, и, в результате, отыскивается лучший индивид во
всей популяции [2]. Данное направление является достаточно перспективным,
однако, на данном этапе будем рассматривать автоматизированную выработку
алгоритмов поведения робота, используя одну вычислительную машину.
Обобщенная схема модели интерпретации
макрокоманд робота представлена на рисунке 1. Такую модель очень удобно
интерпретировать и обрабатывать в вычислительной машине.
Рисунок 1 – Модель представления алгоритма на языке
макрокоманд робота
Модель представления алгоритма на языке макрокоманд
робота состоит из двух частей: статической и динамической.
Статическая часть представляет собой общий алгоритм
функционирования интеллектуального агента, который не меняется в пределах
решаемой задачи. Основной механизм работы интеллектуального агента заключается
в повторении некоторых действий в цикле и проверки условий, требуемых задачей.
Действия определяются экспертом и отвечают на вопрос: что требуется сделать по
условию задачи.
Рассмотрим задачу нахождения и сбивания кегель.
Главная цель: сбить все требуемые объекты за минимальное время, не выходя за
пределы доступной зоны. Это значит, что статическая часть модели интерпретации
макрокоманд робота будет содержать два цикла с предусловием, а также
операторные скобки, в которых расположится динамическая часть модели. Первый
цикл работает до тех пор, пока не будут сбиты все кегли (допустим, мы знаем
фиксированное число объектов). Вложенный цикл работает до тех пор, пока не
будет обнаружена и сбита каждая очередная кегля. Статическая часть модели
представлена на рисунке 2.
Рисунок 2 – Статическая часть модели представления
макрокоманд робота
Динамическая часть модели изображена на рисунке 3. Эта
часть формируется программно и в свою очередь может быть разделена на две
области. Назовем их область А и область Б.
Область А представляет собой
совокупность последовательных движений робота, либо иных действий, которые
могут потребоваться при решении той или иной задачи. Нас будет интересовать
стратегия поведения робота, представленная совокупностью движений платформы,
характеризующихся скоростью и временем выполнения. Именно здесь происходит
выработка стратегии робота с помощью генетического алгоритма.
Область Б
занимается формированием различных воздействий в ответ на факторы окружающей
среды. При движении робот постоянно сканирует некоторый сектор, оценивает
расстояние, включает или выключает свет при необходимости и так далее. Кроме того,
оценив возникшую ситуацию, он должен своевременно отреагировать на нее. При
идентификации кегли в зоне видимости робот принимает решение о том, как ее
сбить. Учитывается масса, размер объекта, параметры самого робота, состояние и
тип дорожного полотна. При этом
интеллектуальный агент не должен выходить за пределы выделенной
условиями задачи сектора больше чем на допустимый промежуток времени. Однако
решение данной задачи требует больших вычислительных затрат, поэтому в рассматриваемой
работе область Б представляет собой фиксированные
действия, которые мы считаем наиболее приемлемыми в рамках решаемой задачи, и
которые оправдали себя в ходе экспериментов. Заметим, что размер каждого блока,
изображенного пунктиром на рисунке 3, может быть произвольным. Фактически
каждый подобный блок – древовидная модель частного алгоритма, включающая любые
блоки модели интерпретации кода и модели представления, формирующееся
с помощью типовых элементов по всем правилам построения модели интерпретации
программного кода. Именно эта область подлежит оптимизации, внося необходимую
гибкость.
Частный алгоритм из области Б может выглядеть следующим образом. Предположим
робот увидел кеглю. Самый простое решение на текущий момент,
при наличии учитываемого железа – выставить произвольную скорость, например в
50% и ехать в сторону кегли. Однако кегля может обладать большей массой,
высотой; кроме того нам надо максимально быстро разогнаться. В то же время,
большая скорость на скользкой поверхности подвергнет решение задачи на риск. В
таком случае определение стратегии поведения при возникшей ситуации должно быть
выработано системой.
Рисунок 3 - Динамическая часть модели интерпретации
макрокоманд робота
Основная идея способа автоматизированной выработки
алгоритма поведения интеллектуального агента заключается в генерации
динамической части генетическим алгоритмом и последующем соединении статической
и динамической частей. Такая комбинация представляет
стратегию поведения робота, оптимизированную под решаемую задачи с учетом
различных факторов окружающей среды.
Предложен способ автоматизированной выработки
алгоритмов поведения интеллектуального агента, представляющего собой робота,
способного решать поставленную задачу автономно, с учетом условий окружающей
среды. Разработанный механизм использует в основе модель интерпретации
макрокоманд робота, что облегчает процесс формирования стратегий и реализации
генетического алгоритма.
В качестве дальнейшей работы планируется формировать
решение задачи на основе конкурентной эволюции с двумя популяциями, в которой
решение ищется путем противоборства роботов, пытающихся сбить кегли за
минимальное время, и кеглей, пытающихся найти расстановку, которую сложнее
определить и сбить.
Литература
1.
Земских Л.В., Самаров Е.К., Жданов А.А., Бабкова
В.В. Применение генетических алгоритмов для оптимизации адаптивной системы
управления мобильного робота на параллельном вычислительном комплексе / Л.В.
Земских, Е.К. Самаров, А.А.Жданов, В.В. Бабкова // Труды Института системного программирования РАН.
– 2004. – том 7. – С.79-104
2. Сорокин Е.В. Модель интерпретации кода программ / Е.В. Сорокин // Сборник материалов областного конкурса студенческих научных работ 2012 года. – Смоленск, 2012. – С.176-182.
Methods and software for automated behavior generation
algorithms of an intelligent agent
Sorokin E. V.
This paper
introduces methods and software for automated generation behavior algorithms of
an intelligent agent using genetic algorithm to produce strategic solutions. A
new methods of behavior algorithms for intelligent
agent using a model of algorithm interpretation based on a robot macro command
language is offered. The simulation model, using OpenGL library in the
programming environment Delphi 7, is developed for the generation and evaluation
of algorithms.
Key words: code interpretation model, a model of an
interpretation the algorithm based on macro language of the robot, a genetic
algorithm.
Сорокин
Евгений Владимирович, аспирант
Филиал ФГБОУ ВПО «Национальный исследовательский университет МЭИ» в г. Смоленске
Кафедра вычислительной техники