Реферат: Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов

Санкт-Петербургский Государственный Университет информационных технологий, механики и оптики

Факультет информационных технологий и программирования

Кафедра компьютерных технологий


Царев Федор Николаевич


Разработка метода совместного применения генетического программирования и конечных автоматов


Научный руководитель – докт. техн. наук, профессор Шалыто А. А.


Санкт-Петербург

2007


Глава 1.Оглавление
Глава 1. Оглавление 4

Введение 5

^ Глава 2. Общие концепции генетического и автоматного программирования 8

Глава 3. Задача об «Умном муравье» 15

Глава 4. Задача «Летающие тарелки» 25

Заключение 55

Список источников 57


Введение
^ Генетические алгоритмы являются одним из современных и быстро развивающихся направлений в искусственном интеллекте. С их помощью могут быть найдены решения многих задач в различных областях. Примерами таких задач являются: задачи синтеза расписаний, задачи планирования работ и распределения ресурсов, задачи маршрутизации транспортных средств, синтез топологии сетей различного назначения, построение искусственных нейронных сетей, деревьев принятия решений, автоматическое построение программ, проектирование мультиагентных систем, конечных автоматов и клеточных автоматов. К сожалению, в нашей стране этой области уделяется мало внимания. Одна из задач работы – хотя бы частично восполнить этот пробел.

^ Генетическое программирование – разновидность генетического алгоритма, в которой вместо низкоуровневого представления объектов (битовые строки) используется высокоуровневое представление: деревья разбора программ, диаграммы переходов конечных автоматов, и т.д. С помощью генетического программирования наиболее эффективно решаются задачи автоматического построения программ, конечных автоматов, клеточных автоматов.

^ Автоматное программирование – парадигма программирования, при использовании которой программу предлагается строить в виде совокупности поставщиков событий, объектов управления и системы управляющих взаимодействующих конечных автоматов. Поставщик событий характеризуется множеством событий, которые он может генерировать. Объект управления характеризуется множеством вычислительных состояний, а также двумя наборами функций: множеством предикатов, отображающих вычислительное состояние в логическое значение (истина или ложь), и множеством действий, позволяющих изменять вычислительное состояние. Управляющий автомат определяется конечным множеством управляющих состояний, функцией переходов и функцией действий.

Управляющие конечные автоматы часто характеризуются сложным поведением, как например, в задачах об «Умном муравье» и «Летающие тарелки», рассматриваемых в настоящей работе. В таком случае их проектирование представляет собой весьма трудоемкую задачу. Эта задача становится еще более сложной в случае проектирования системы взаимодействующих автоматов или в случае наличия в системе нескольких взаимодействующих агентов, каждый из которых управляется отдельным автоматом. Возникает естественное желание – автоматизировать процесс проектирования автоматов, поручив основную работу компьютеру.

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

Рассматриваемые в работе задачи выбраны не случайно. Задача об «Умном муравье» достаточно хорошо изучена. Сравнение результатов применения разработанного в настоящей работе алгоритма генетического программирования позволяет установить его эффективность – с его помощью построен решающий эту задачу автомат, содержащий меньшее, чем известные ранее автоматы, количество состояний. Задача-игра «Летающие тарелки» предлагалась на заочном туре Всесибирской олимпиады по информатике 2005 года. Она представляет собой пример задачи, в которой необходимо построить несколько автоматов, управляющих агентами. Кроме этого, существуют построенные вручную решения этой задачи, с которыми можно сравнить построенное автоматически.

В заключение работы анализируются ее результаты, и приводится ряд открытых вопросов и направлений для дальнейших исследований в этой области.
^ Глава 2.Общие концепции генетического и автоматного программирования Генетические алгоритмы
Генетический алгоритм (genetic algorithm) [1–4] представляет собой стохастический метод оптимизации. Основная идея генетических алгоритмов состоит в использовании принципа естественного отбора, который составляет основы теории эволюции живых организмов, предложенной Чарльзом Дарвином.

Основы генетических алгоритмов были заложены Дж. Холландом (J. Holland) – в 1975 году он опубликовал книгу «Адаптация в естественных и искусственных системах». Описанный в ней подход был в дальнейшем развит Холландом и его учениками в Мичиганском университете.

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

В генетическом алгоритме все то же самое. В качестве особей выступают элементы пространства возможных решений некоторой задачи (маршруты коммивояжера, диаграммы переходов автомата и т. п.). Задан набор генетических операций, с помощью которых из существующих особей формируются новые. Кроме этого определена так называемая функция приспособленности (fitness-function), которая показывает, насколько «хорошим» решением задачи является особь.

Процесс работы генетического алгоритма состоит в генерации поколений особей до тех пор, пока не будет выполнено некоторое условие останова (например, достигнуто целевое значение функции приспособленности или сгенерировано заданное число поколений). На рис. 1 приведена общая схема работы генетического алгоритма.



Рис. 1. Общая схема работы генетического алгоритма

По сравнению с традиционными методами оптимизации генетические алгоритмы имеют ряд преимуществ:

генетические алгоритмы легко модифицируются для параллельных вычислений;

они хорошо подходят для оптимизации недиффернцируемых функций.

Основными недостатками генетических алгоритмов являются:

высокая трудоемкость, ограничивающая их область применения;

сложность оценки степени пригодности конкретных генетических операций для конкретной задачи.
^ 2.1.1Традиционный генетический алгоритм
В этом разделе приведено краткое описание традиционного генетического алгоритма (conventional genetic algorithm) [4] с одноточечной рекомбинацией и мутацией. В этом алгоритме каждая особь представляет собой битовую строку длины l, а размер популяции равен n.

Шаг 1. Генерации начальной популяции . Для этого, например, можно сгенерировать n битовых строк, в которых каждый из l битов равен 0 или 1 с одинаковой вероятностью.

Шаг 2. Вычислить функцию приспособленности f(x) для каждой особи из текущей популяции. Этот шаг обычно является наиболее трудоемким по времени во всем алгоритме. Отметим, что при вычислении функции приспособленности, как правило, необходимо осуществить декодирование некоторого объекта из двоичной строки.

Шаг 3. Переход к следующему поколению популяции. При создании нового поколения могут использоваться различные стратегии. Далее будет описан так называемый алгоритм рулетки (roulette wheel selector) [2].

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

После этого с некоторой наперед заданной вероятностью происходит рекомбинация (кроссовер, скрещивание) родительских особей. В результате образуются их «потомки» - z1 и z2. Происходит это следующим образом: случайно (с равномерным распределением на множестве {1, 2, …, l}) выбирается число k. Хромосомы «потомков» z1 и z2 теперь строятся следующим образом: для z1 – первые k символов совпадают с первыми k символами x, последние (l-k) – с последними (l-k) символами y, для z2 – наоборот. Например, если l=7, x=1001010, y=0001001, k=3, то z1=1001001, z2=0001010. «Забудем» теперь о «родителях» x и y, обозначив x=z1, y=z2.

После этого равновероятно выбирается одна из особей x либо y – выбранную особь обозначим как z.

С некоторой (как правило, порядка 0.01) вероятностью происходит мутация особи z – в ней случайно выбирается один бит и изменяется.

Получившаяся в результате особь z добавляется в следующее поколение.

Шаг 4. Повторять шаги 2 и 3 до тех пор, пока не будет выполнено условие останова (максимальная приспособленность в популяции достигла целевого значения, прекратился рост максимальной приспособленности, число поколений достигло некоторого предела и т.д.).

Отметим, что кроме описанных выше одноточечного кроссовера, алгоритма рулетки и мутации изменением случайного бита, существуют и другие методы – обзор таких методов приведен в [5].
^ 2.1.2Математический аппарат традиционного генетического алгоритма
Вопрос о том, почему традиционный генетический алгоритм работает, то есть происходит в вероятностном смысле постепенная оптимизация функции приспособленности обсуждается в [3, 6–9]. В [3,9] приводится, по сути неформальное, объяснение функционирования генетических алгоритмов, в [6] – формализованное, но при условии достаточно сильных ограничений на функцию приспособленности. Математическая модель традиционного генетического алгоритма описана в [7, 8].
^ Генетическое программирование
Генетическое программирование (genetic programming), предложенное J.R. Koza в 1992 году [9], – это применение генетических алгоритмов для автоматизированного построения программ.

Основным отличием генетического программирования от традиционных генетических алгоритмов является способ кодирования особей. Если в генетическом алгоритме особи кодируются с помощью битовых строк, то в генетическом программировании используется более высокоуровневое представление: используются деревья разбора, тексты программ на языках программирования с несложной структурой (например, на языке Lisp) и т. д.

Такой подход позволяет определить генетические операции скрещивания и мутации, которые лучше подходят для решаемой задачи. Например, если каждая особь представляет собой программу, то возможны так называемые операции, изменяющие архитектуру, (architecture-altering operations) – например, добавление подпрограммы [10].
^ Автоматное программирование
Автоматное программирование [11–16] – парадигма программирования, предложенная А.А. Шалыто. При использовании этой парадигмы программы проектируются так же, как системы управления технологическими процессами – выделяются поставщики событий, объекты управления и система управления, которая представляет собой систему взаимодействующих конечных автоматов (рис. 2).



Рис. 2. Схема программы в автоматном программировании

Поставщик событий характеризуется множеством событий (обозначены на рис. 2 как e), которые он может генерировать. Объект управления характеризуется множеством вычислительных состояний, а также двумя наборами функций: множеством предикатов (обозначены на рис. 2 как x), отображающих вычислительное состояние в логическое значение (истина или ложь), и множеством действий, позволяющих изменять вычислительное состояние. Управляющий автомат определяется конечным множеством управляющих состояний, функцией переходов и функцией действий.

Если говорить более формально, задано множество событий , вырабатываемых поставщиком событий, множество предикатов и множество действий , которые связаны с объектом управления. Управляющий автомат характеризуется конечным множеством состояний S, начальным состоянием s0, функцией перехода φ: S×E×2X→S и функцией действий a: S×E×2X→2Z. Таким образом, выбор перехода зависит от текущего состояния автомата, поступившего события и значений предикатов, а при переходе в новое состояние производятся некоторые действия.

Автоматное программирование успешно применяется при создании программного обеспечения реактивных систем, таких как, например, некоторые мультиагентные системы [13–16].

Для поддержки автоматного программирования существует инструментальное средство ^ UniMod [18, 19]. UniMod позволяет строить и редактировать схемы связей и диаграммы состояний, обеспечивать проверку формальной корректности этих диаграмм, проводить отладку диаграмм в графическом режиме и т. д.

После построения диаграмм и автоматической проверки их корректности, по ним строится их ^ XML-описание. Далее вручную пишутся следующие фрагменты программы на языке Java: для поставщиков событий – их объявления, инициализация и преобразование системных событий в автоматные, а для объектов управления – методы, реализующие входные переменные и выходные воздействия.

Инструментальное средство UniMod применялось автором при решении задачи «Летающие тарелки» без использования генетического программирования [16, 17].
^ Несколько задач, в которых генетические алгоритмы применяются для построения автоматов
Приведем список таких задач:

итерированная дилемма заключенного (iterated prisoner’s dilemma) [4, 20];

задача классификации плотности для клеточных автоматов (density classification task for cellular automata) [21, 22];

задача синхронизации для клеточных автоматов (synchronization task for cellular automata) [23];

задача упорядочивания для клеточных автоматов (ordering task for cellular automata) [24];

задача о «Флибах» [25, 26];

задача об «Умном муравье» (artificial ant problem) [3, 27, 28] – одна из задач, рассматриваемых в настоящей работе.


^ Глава 3.Задача об «Умном муравье» 3.1Постановка задачи
Приведем описание задачи об «Умном муравье» [27]. Игра происходит на поверхности тора размером 32 на 32 клетки (рис. 3). В некоторых клетках (обозначены на рис. 3 черным цветом) находится еда. Она расположена вдоль некоторой ломаной, но не во всех ее клетках. Клетки ломаной, в которых нет еды, обозначены серым цветом. Белые клетки не содержат еду и не принадлежат ломаной. Всего на поле 89 клеток с едой. Отметим, что рассматриваемое игровое поле называется John-Muir Trail [27].



Рис. 3. Игровое поле

В клетке, помеченной меткой «Start», в начале игры находится муравей. Он занимает одну клетку и смотрит в одном из четырех направлений (север, юг, запад, восток). В начале игры муравей смотрит на восток.

Муравей умеет определять находится ли непосредственно перед ним еда. За один игровой ход муравей может совершить одно из четырех действий:

сделать шаг вперед, съедая еду, если она там находится;

повернуть налево;

повернуть направо;

ничего не делать.

Съеденная муравьем еда не восполняется, муравей жив на протяжении всей игры, еда не является необходимым ресурсом для его жизни. Ломаная не случайна, а строго фиксирована. Муравей может ходить по любым клеткам поля.

Игра длится 200 ходов, на каждом из которых муравей совершает одно из четырех действий. По истечении 200 ходов подсчитывается количество еды, съеденной муравьем. Это значение и есть результат игры.

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

Один из способов описания поведения муравья – конечный автомат с действиями на переходах (автомат Мили), у которого есть одна входная переменная логического типа (находится ли еда перед муравьем), а множество выходных воздействий состоит из четырех упомянутых выше элементов.

Например, эвристически построенный автомат из [27], граф переходов которого изображен на рис. 4, описывает поведение муравья, который съедает 81 единицу еды за 200 ходов, а всю еду – за 314 ходов.



Рис. 4. Эвристически построенный автомат с пятью состояниями


Поясним используемые на рис. 4 обозначения. Пометки на переходах имеют формат условие / действие. Условия обозначаются следующим образом:

F – перед муравьем есть еда;

!F – перед муравьем нет еды.

Действия обозначаются следующим образом:

M – «Сделать шаг вперед»;

L – «Повернуть налево»;

R – «Повернуть направо»;

N – «Ничего не делать».
^ 3.2Известные решения задачи об «Умном муравье»
Для решения задачи об «Умном муравье» в [3, 27, 28] применялись различные генетические алгоритмы. Однако построенные в указанных работах автоматы содержат от восьми до тринадцати состояний. В настоящей работе с помощью генетического программирования построен автомат, содержащий семь состояний.

В [3] описан генетический алгоритм, позволяющий построить автомат из восьми состояний, позволяющий муравью съесть всю еду. В этом алгоритме автоматы кодировались битовыми строками, и при этом использовалась перенумерация состояний (SFS = Standardizing transitions to the Future or next States, MTF = Move To Front), позволяющая проще находить изоморфные автоматы и, таким образом, ускорить сходимость алгоритма.

В [27] для построения автоматов также используется генетический алгоритм с кодированием особей в виде битовых строк. Он представляет собой улучшенную версию алгоритма из [28]. Улучшение состоит в использование так называемого замораживания (freezing) состояний и переходов. Замораживание состоит в том, что некоторые состояния и переходы не могут быть изменены при мутации. При этом множество замороженных состояний и переходов также меняется в процессе работы генетического алгоритма. С помощью этого алгоритма были построены автоматы из 11 и 13 состояний.
^ 3.3Предлагаемый метод решения задачи об «Умном муравье»
В настоящей работе для решения задачи об «Умном муравье» предлагается использовать генетическое программирование. Ниже приведено описание разработанного алгоритма генетического программирования.

Алгоритм генетического программирования состоит из пяти частей:

создание начального поколения;

мутация;

скрещивание (кроссовер);

отбор особей для формирования следующего поколения;

вычисление функции приспособленности (фитнес-функции).

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

Хромосома представляется не в виде битовой строки, как в генетических алгоритмах, а в виде объекта в языке программирования Java. Этот объект имеет описанную структуру:

public class Automaton {

public Transition[][] transitions;

public int initialState;

public int stateCount;

}

^ Создание начального поколения. Начальное поколение состоит из фиксированного числа случайно сгенерированных автоматов. Все автоматы в поколении имеют одинаковое наперед заданное количество состояний.

Мутация. При мутации случайно выбирается один из четырех равновероятных вариантов:

изменение начального состояния – в этом случае новое начальное состояние выбирается случайно и равновероятно;

изменение действия на переходе – случайно и равновероятно выбирается переход, и действие на нем изменяется на случайное. При этом все возможные действия равновероятны;

изменение состояния, в которое ведет переход, – случайно и равновероятно выбирается переход. После этого состояние, в которое ведет переход, заменяется на случайно выбранное состояние;

изменение условия на переходе – случайно и равновероятно выбирается состояние. После этого переходы из этого состояния, соответствующие условиям «Перед муравьем есть еда» и «Перед муравьем нет еды», меняются местами.

Скрещивание. Оператор скрещивания получает на вход две особи и выдает также две особи. Процесс скрещивания происходит следующим образом. Обозначим родительские особи P1 и P2, а потомков – S1 и S2.

Обозначим начальное состояние автомата A как A.is. Тогда для потомков S1 и S2 будет верно одно из двух: либо S1.is = P1.is и S2.is = P2.is, либо S1.is = P2.is и S2.is = P1.is, причем оба варианта равновероятны.

Опишем, как «устроены» переходы автоматов-потомков S1 и S2 –может быть реализован один из двух равновероятных вариантов.

Первый вариант скрещивания. Обозначим переход из состояния номер i в автомате P1 по значению входной переменной «Перед муравьем есть еда» как P1(i, 1), а по значению «Перед муравьем нет еды» как P1(i, 0). Аналогичный смысл придадим обозначениям P2(i, 0) и P2(i, 1). Тогда для переходов из состояния с номером i в автоматах-потомках S1 и S2 будет справедливо одно из четырех:

либо S1(i, 0) = P1(i, 0), S1(i, 1) = P2(i, 1) и S2(i, 0) = P2(i, 0), S2(i, 1) = P1(i, 1);

либо S1(i, 0) = P2(i, 0), S1(i, 1) = P1(i, 1) и S2(i, 0) = P1(i, 0), S2(i, 1) = P2(i, 1);

либо S1(i, 0) = P1(i, 0), S1(i, 1) = P1(i, 1) и S2(i, 0) = P2(i, 0), S2(i, 1) = P2(i, 1);

либо S1(i, 0) = P2(i, 0), S1(i, 1) = P2(i, 1) и S2(i, 0) = P1(i, 0), S2(i, 1) = P1(i, 1).

Все четыре варианта равновероятны.

Второй вариант скрещивания. В автоматах P1 и P2 найдем переходы, которые они выполняют в течение первых сорока ходов по игровому полю. Обозначим множество таких переходов автоматов P1 и P2 как TF(P1) и TF(P2) соответственно. Множество переходов некоторого автомата A обозначим T(A). Возможны два равновероятных варианта:

либо и ;

либо и .

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

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

Кроме этого, если на протяжении достаточно большого числа поколений не происходит увеличения приспособленности, то применяются «малая» и «большая» мутации поколения. При «малой» мутации поколения ко всем особям, кроме 10% лучших, применяется оператор мутации. При «большой» мутации каждая особь либо мутирует, либо заменяется на случайно сгенерированную.

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

^ Вычисление функции приспособленности. Функция приспособленности особи (автомата) равна , где F –количество еды, которое съедает за 200 ходов муравей, поведение которого задается этим автоматом, а T – номер хода, на котором муравей съедает последнюю единицу еды. Она вычисляется моделированием и запоминается. Таким образом, для каждой особи функция приспособленности вычисляется один раз.

Настраиваемые параметры алгоритма. Следующие параметры алгоритма генетического программирования могут быть изменены:

размер поколения;

доля особей, переходящих в следующее поколение;

количество состояний;

вероятность мутации;

время до «малой» мутации поколения;

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

Отметим, что действие «Ничего не делать» бесполезно и, в некотором смысле, подобно ε-переходам в конечных недетерминированных автоматах, используемых для распознания регулярных языков. Поэтому оно может быть устранено из автоматов алгоритмом, подобным алгоритму ε-замыкания [29]. Таким образом, можно считать, что в автоматах используются только три действия (идти вперед, повернуть направо, повернуть налево).

С помощью описанного алгоритма генетического программирования был построен автомат из семи состояний (рис. 5), решающий задачу об «Умном муравье» за 193 хода. Этот автомат был построен за 130000 поколений, при этом было проанализировано 160 миллионов автоматов. Процесс построения занял порядка четырех часов на компьютере с процессором Intel Celeron M 1.5 GHz.



Рис. 5. Автомат из семи состояний, построенный алгоритмом генетического программирования

Отметим, что при повторном запуске алгоритма после анализа 230 миллионов автоматов, содержащих семь состояний, также был найден автомат, решающий задачу об «Умном муравье». Построить автомат, содержащий менее семи состояний не удалось. Наилучший автомат из пяти состояний, который удалось построить, позволяет муравью съесть 83 единицы еды, из шести состояний – 85 единиц еды.

Также с помощью разработанного алгоритма было построено семейство автоматов, решающих задачу об «Умном муравье» и содержащих восемь состояний. В табл. 1 приведена краткая сводка применения описанного алгоритма к построению автоматов из восьми состояний.

Таблица 1. Результаты применения алгоритма для построения автомата из восьми состояний

^ Размер поколения

Доля особей, переходящих в следующее поколение

Время до «малой» мутации поколения

Время до «большой» мутации поколения

^ Количество вычислений функции приспособленности

1000

0.3

100

150

1370300

1000

0.4

100

150

1235700

1000

0.5

100

150

4055200

1000

0.4

100

150

2992300

1000

0.4

100

150

1418300

1000

0.4

100

150

189400

1000

0.4

100

150

220300

1000

0.3

100

150

1948400

2000

0.5

100

150

1540000



Отметим также, что вопрос о существовании автоматов, позволяющих муравью съесть всю еду и содержащих при этом менее семи состояний, остается открытым.
^ Глава 4.Задача «Летающие тарелки» 4.1Постановка задачи
Приведем постановку задачи «Летающие тарелки» [16, 17, 30]. Проводится соревнование между двумя командами летающих тарелок. Цель соревнований состоит в том, чтобы одна из тарелок команды переместилась на максимальное расстояние от линии старта. Состязание проходит на трассе, представляющей собой полубесконечную (бесконечную в одну сторону) полосу шириной 40 метров. Маневры, связанные с изменением высоты полета, не допускаются (таким образом, трасса соревнования двумерна).

Каждая команда состоит из N тарелок (агентов). В дальнейшем, кроме термина «соревнование», будем использовать термин «гонка».

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

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

Каждый агент имеет определенный запас топлива, расходуемого в процессе движения. По команде «Старт» все агенты начинают движение с целью максимально удалиться от линии старта. Агенты в процессе полета могут изменять скорость своего движения за счет изменения расхода топлива.

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

Управление каждой командой выполняет программа, написанная на языке программирования Java.
^ 4.1.1Правила соревнований
В каждом соревновании каждая из команд на старте имеет N летающих тарелок с полным запасом топлива (10 см3). Исходно тарелки первой команды случайным образом располагаются на первых 25 метрах левой половины трассы. Тарелки второй команды располагаются симметрично им в правой половине трассы (рис. 6).



Рис. 6. Летающие тарелки на старте

Жизненный цикл летающей тарелки выглядит следующим образом. Она может находиться в одном из трех состояний: «Полет», «Нормальное завершение гонки», «Аварийное завершение гонки» (рис. 7).



Рис. 7. Возможные состояния летающей тарелки и переходы между ними

Обозначения, используемые на рис. 7, приведены в табл. 2.

Таблица 2. Используемые обозначения

Обозначение

Описание

e1

Летающая тарелка покинула пределы трассы (ее центр пересек границу трассы)

e2

Скорость летающей тарелки стала меньше, чем один м/с

e3

Летающая тарелка столкнулась с другой летающей тарелкой

v_rel

Относительная скорость столкновения летающих тарелок

fuel

Количество топлива, которое осталось у летающей тарелки


Поясним поведение летающей тарелки. В начале гонки она находится в воздухе, исправна и способна продолжать участие в гонке. Этому соответствует состояние «Полет».

При выходе летающей тарелки за пределы трассы (событие e1) она завершает гонку аварийно.

Если скорость летающей тарелки падает ниже одного м/с (событие e2), и ее топливный бак не пуст (условие fuel != 0), то она завершает гонку аварийно. Если же при падении скорости ниже одного м/с (событие e2) топливный бак летающей тарелки пуст (условие fuel == 0), то она нормально завершает гонку.

Если летающая тарелка сталкивается с другой тарелкой (событие e3), то при относительной скорости столкновения, большей одного м/с (условие v_rel > 1), тарелка аварийно завершает гонку. При относительной скорости столкновения, не превышающей одного м/с (условие v_rel <= 1), тарелка продолжает полет.

Заметим, что поскольку начальный запас топлива у каждой тарелки конечен, то рано или поздно все тарелки обеих команд завершат гонку.

При подведении итогов гонки учитываются только результаты тарелок, нормально ее завершивших. Результатом команды считается наибольшее из расстояний, на которое удалились от линии старта ее летающие тарелки, нормально завершившие гонку. Если все летающие тарелки команды вышли из гонки аварийно, результат команды считается равным нулю. Победителем признается команда, прошедшая наибольшее расстояние. В случае равенства результатов гонка считается завершившейся вничью.
^ 4.1.2Динамика летающей тарелки
Летающая тарелка представляет собой дискообразное "летающее крыло" радиусом один метр. На рис. 8 представлен вид сверху летающей тарелки.



Рис. 8. Летающие тарелки на старте

Тарелка имеет реактивный двигатель (на рис. 8 он условно показан горизонтальным прямоугольником), топливный бак (вертикальный прямоугольник) емкостью 15 см3, аэродинамические рули и бортовой компьютер, способным регулировать расход топлива (и, как следствие, тягу двигателя) и положение аэродинамических рулей. Эти рули позволяют тарелке маневрировать. Тарелка может передвигаться со скоростями от одного метра в секунду. Максимальная скорость тарелки зависит от запаса топлива и сопротивления воздуха. Ограничение в один метр в секунду вызвано тем, что летающая тарелка с меньшей скоростью не может держаться в воздухе.

Летающая тарелка движется в соответствии со вторым законом Ньютона. Ее движение определяется двумя силами: сопротивлением воздуха F и тягой двигателя T. Если тяга не равна сопротивлению воздуха, то летающая тарелка движется с ускорением, которое может быть положительным (если тяга больше сопротивления воздуха) или отрицательным (если сопротивление воздуха больше тяги).

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

Сопротивление воздуха определяется по формуле , где v – скорость тарелки, а коэффициенты с1 и с2 определяются ее аэродинамическими характеристиками и одинаковы для всех тарелок обеих команд.

Тяга двигателя определяется по формуле , где q – расход топлива в сантиметрах кубических в секунду. Расход топлива находится под контролем бортового компьютера тарелки, что позволяет изменять расход от нуля до единицы. Константа c4 определяется характеристиками двигателя тарелки и одинакова для всех тарелок обеих команд.

Аэродинамические рули позволяют летающей тарелке поворачивать относительно ее текущего направления движения на угол, не превышающий 25°.
^ 4.1.3Аэродинамическое взаимодействие между летающими тарелками
При полете летающей тарелки от траектории ее полета в направлениях назад и в стороны под углом около 30° распространяются конические вихревые потоки воздуха. Если другая тарелка попадет в этот вихрь, то сопротивление воздуха ее полету резко снизится (рис. 9).



Рис. 9. Летающие тарелки на старте

Отметим что, летающая тарелка, находящаяся за хвостом (два сектора по 20°) другой летающей тарелки, испытывает дополнительное сопротивление движению, обусловленное реактивной струей.

Поясним, как учитывается изменение сопротивления воздуха. Если центр второй летающей тарелки находится в областях, отмеченных на рис. 4 знаком "+", сопротивление воздуха ее движению падает на 50%. Если же центр второй тарелки находится в области, помеченной знаком "–", сопротивление воздуха возрастает на 50%.

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



Рис. 10. Наложение областей аэродинамического взаимодействия двух летающих тарелок

Учитывая изложенное, вычисление сопротивления воздуха происходит следующим образом. Пусть N+ – количество тарелок, уменьшающих сопротивление воздуха в этой области, а N- – количество тарелок, увеличивающих сопротивление воздуха. Пусть ΔN = N+ – N-. Если ΔN = 0, то в этой области нормальное аэродинамическое сопротивление, если ΔN = 1 или ΔN = 2, то сопротивление понижается на 50ΔN процентов. Если ΔN отрицательно, то сопротивление в этой области повышается на 50|ΔN| процентов.
^ 4.1.4Столкновение летающих тарелок
При столкновении двух тарелок происходит их абсолютно упругое соударение без передачи вращательного момента. Если относительная скорость столкновения была более одного метра в секунду, то обе участвовавшие в столкновении летающие тарелки повреждаются и начинают терять высоту. При этом они обе аварийно завершают гонку.

Под относительной скоростью столкновения понимается проекция векторной разности скоростей летающих тарелок на прямую, проходящую через центры летающих тарелок в момент столкновения (рис. 11). Вектор Vrel соответствует относительной скорости.



Рис. 11. Относительная скорость столкновения двух летающих тарелок
^ 4.1.5Моделирование гонки
Моделирование гонки происходит по ходам, каждый из которых занимает t миллисекунд (параметр t читае