Об автоматной модели преследования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

09460

На правах рукописи УДК 519.71

74£

Волков Николай Юрьевич ОБ АВТОМАТНОЙ МОДЕЛИ ПРЕСЛЕДОВАНИЯ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

МОСКВА- 2010

004601748

Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научный руководитель — доктор физико-математических наук, профессор

Валерий Борисович Кудрявцев

Официальные оппоненты:

доктор физико-математических наук, профессор Сергей Андреевич Ложкин

кандидат физико-математических наук, доцент Игорь Андреевич Лавров

Ведущая организация — Московский Энергетический Институт

(Технический университет)

Защита диссертации состоится 14 мая 2010 г. в 16 ч. 45 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете им. М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 14 апреля 2010 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

А.О.Иванов

Общая характеристика работы

Актуальность темы

Целью работы является постановка и решение задачи математического моделирования процесса преследования группой хищников группы жертв. Геометрия пространства, в котором происходит преследование, моделируется шахматным лабиринтом (т.е. графом определенного вида). Механизмы восприятия и принятия решений перемещающихся объектов - «хищников» и «жертв» моделируется при помощи конечного автомата. Таким образом, задача преследования получает автоматную трактовку и решается в этой постановке методами дискретной математики.

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

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

Автоматный подход к решению задачи преследования впервые был применен в 1987 г. В. И. Грунской 2. В этой работе рассматривалось взаимодействие двух конечных автоматов У/ та 2 - «хищника» и «жертвы» в шахматных лабиринтах, имеющих вид квадрата со стороной I. Хищники и жертвы обладали способностью видеть происходящее в клетках, соседних с той, в которых они находились и перемещаться за 1 такт на одну клетку по вертикали, по горизонтали или оставаться на месте. Было показано, что для любых 1,п £ N существует IV с числом состояний 0(п ■ 12)1 который ловит за время 0(п ■ I4) любой автомат-жертву И с числом состояний не большим п, в квадрате со стороной, не большей при любом начальном расположении и 2. Также было установлено, что не существует автомата ловящего любой 2 в произвольном квадрате с фиксированной длиной стороны 1,1> 8.

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

1В.Волиерра. Математическая теория борьбы за существование, Москва, 2004.

аГрунская В.И., О динамическом взаимодействии автоматов, в кн.: Математическая кибернетика

' и ее приложения к биологии, МГУ, 1987, стр. 8-18.

обзор.

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

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

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

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

имеет возможность реагировать на жертв, попавших в его зону обзора).

Жертва считается пойманной, если она оказалась в фиксированной окрестности одного из хищников. Такая жертва исчезает из лабиринта. Система жертв поймана, если пойманы все жертвы.

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

Фиксируем скорости и обзоры хищников и жертв.

Цель работы

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

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

Структура и объем диссертации

Диссертационная работа изложена на 117 страницах и состоит из введения и 4 глав, разбитых на параграфы. Библиография включает 9 наименований.

Научная новизна

1. Предложена автоматная модель преследования одной системой объектов другой системы объектов в широком классе геометрических сред.

Исследованы два основных способа взаимодействия каждой из состязающихся команд — независимое друг от друга поведение и коллективное взаимодействие. На ряде убедительных примеров показаны принципиальные преимущества алгоритмов коллективного взаимодействия.

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

3. Доказана способность коллективов автоматов осуществлять универсальную поимку произвольных систем жертв в широком классе бесконечных лабиринтов.

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

Основные методы исследования

В диссертации использованы методы теории автоматов, теории алгоритмов и элементы дискретной геометрии.

Теоретическая и практическая ценность работы

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

Апробация работы

Результаты диссертации неоднократно докладывались на семинарах механико-математического факультета МГУ им. М.В. Ломоносова «Теория автоматов» (2004-2009 гг.) и «Кибернетика и информатика» (2002-2009 гг.)

под руководством академика В.Б. Кудрявцева, на семинаре «Математические вопросы кибернетики» под руководством академика О.Б. Лупанова в 2006 г.

Они докладывались также на следующих конференциях: международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, МГУ им. Ломоносова, 2006г.), международная конференция «Дискретные модели в теории управляющих систем» (Москва, МГУ им. Ломоносова, 2006г.), конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова (Москва, МГУ им. Ломоносова, 2005, 2006 и 2007 гг.), международные научные конференции студентов, аспирантов и молодых ученых «Ломоносов» (Москва, МГУ им. Ломоносова, 2005, 2006, 2007 и 2008 гг.), научные конференции «Ломоносовские чтения» (Москва, МГУ им. Ломоносова, 2006, 2007, 2008 и 2009 гг.), третья научная конференция студентов и аспирантов кафедры Математической теории интеллектуальных систем механико-математического факультета МГУ (Москва,' МГУ им. Ломоносова, 2007г.).

Публикации по теме диссертации

Основные результаты диссертации опубликованы в четырех статьях [1]—[4], список которых приведен в конце автореферата.

Краткое содержание работы

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

Во второй главе дается формальная постановка задачи, ставится основная проблема и приводятся вспомогательные построения.

Вводятся классы шахматных лабиринтов в которых будет происходить преследование. Это целочисленная плоскость Ь0 = {(х,у)\х,у е 2}), полуплоскость Ь\ = {(г, у) \х е Ъ, у £ К}, семейство бесконечных полос ширины I Ь2{1) — {(х,у)|0 < у < I, х,у семейство бесконечных полуполос ширины I Ьз(1) — {(х, у) 10 < у < I, х,у 6 М}, квадрант = {(х,у)\х,у е К}) и семейство квадратов со стороной I Ьь{1) = {(®,1/)|® < I, У < I, х, у € Н}, где г € N. В дальнейшем будем понимать под Ь один из вышеописанных лабиринтов, т.е. ь € {Ьо, Ьг, ь4} и {Ь2(1) 11 е к} и {¿з(0116 н} и {Ь5(0 11 6 М} 11 6 К}.

Вводится мантхетенская метрика

(р((яът), ЗЛг)) = К - х2\ + |У1 - ш\ )•

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

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

Входной алфавит автомата, перемещающегося в лабиринте определяется как множество пар конфигураций зоны обзора автомата (автомат воспринимает конфигурацию своей окрестности как в моменты своего хода, так и в моменты хода автоматов-противников).

Выходной алфавит автомата определяется как множество всех векторов длины не превосходящей V, где V - скорость данного автомата.

Автоматы-жертвы будут перемещаться все одновременно в четные моменты времени, а автоматы-хищники — в нечетные.

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

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

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

Фиксируются значения скоростей хищников и жертв —У и V, соответственно, а обзоров —Л и В!, соответственно. V, V', Я и В! — произвольные натуральные числа, удовлетворяющие неравенствам К>У,В!>У,

К>В!,У> V'.

Для каждого типа лабиринтов (Ь0, Ь\, 1<4 и Ьь) ставится во-

прос: существует ли коллектив хищников К (В., V), такой что для любого лабиринта Ь данного типа, существует такое начальное расположение хищников в X, что коллектив К ловит произвольную конечную независимую систему жертв в (Я', V'), при любом начальном расположении жертв из Я в лабиринте Ь.

Также в этой главе вводятся два способа описания автоматов, функционирующих в лабиринтах: через схемы функционирования и через композиции ранее построенных автоматов. Схема функционирования системы автоматов - это программа на специальном языке (близком к языку машин Тьюринга), задающая функции переходов и выходов автоматов системы. Схемами функционирования в следующих главах будут задаваться, как правило, не очень большие системы автоматов. Композиция автоматов А и В - это автомат, сначала функционирующий как Л, а после остановки Л - как В. Аналогично определяется композиция коллективов автоматов. При помощи опереации композиции в последующих главах из простых система автоматов конструируются сложные. В главе 2 также построен ряд вспомогательных автоматов, которые будут использоваться в дальнейшем.

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

Теорема 1. При любых натуральных Н, У, И', V', таких, что Я>У и Ш > V', для любой независимой системы автоматов-хищников К(Н, V) = (..., ), любой независимой системы автоматов-жертв Б = (Щ,... ,и„){В!,У) и любых начальных расположений №1,... ,\Ут на. плоскости Ьо существуют такие начальные расположения автоматов 1/г,... ,ип на плоскости, при которых все они убегают от К.

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

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

Невозможность поимки жертв на плоскости независимой системой хищников побуждает исследовать проблему преследования жертв коллективом хищников.

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

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

Теорема 2, Существуют, коллективы хищников К0(Я,У), Кг(Я, V), К2{Я, V"), Кг{Я, V) и К4(Я, V), такие что:

1) Для каждого г ~ 0,1, коллектив К^ стартуя из любого канонического расположения в Ьловит любую конечную независимую систему жертв Я (Я, V — 1) при любом их начальном расположении в Ь,;

2) Для каждого г = 2,3, коллектив для любого I, стартуя из любого канонического расположения в ловит любую конечную независимую систему жертв Я (Я, V — 1) при любом их начальном расположении в

ш-

3) При V > ЗУ' коллектив стартуя из любого канонического расположения в ¿4, ловит любую конечную независимую систему жертв Б [Я, V') при любом их начальном расположении в Ьц.

На плоскости, полуплоскости, в /-полосе и /-полуполосе удалось решить задачу построения такого универсального коллектива хищников за-счет учета периодичности выходной последовательности жертвы в этих лабиринтах. Каждая жертва кодируется рядом натуральных или целочисленных параметров: клеткой старта, периодом и предпериодом выходной последовательности, а также вектором перемещения за период выходной последовательности.

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

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

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

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

При V > ЗУ, т.е. при наличии такого превосходства в скорости, хищник, моделируя движение жертвы, начиная с некоторого момента перемещается по ее траектории быстрее, чем она (потери времени на издержки процесса моделирования становятся пренебрежимо малыми в сравнении с растущей длиной периодических участков траектории). Остальные хищники, осуществляя арифметические операции с параметрами жертвы вычисляют верхнюю оценку момента времени, когда хищник моделирующий жертву окажется впереди нее на ее траектории. В один из последующих моментов осуществляется остановка этого хищника и он ожидает жертву в нужной клетке. Верхняя оценка времени необходимого ожидания также вычисляется остальными автоматами-хищниками. Если по истечении этого времени жертва все еще не поймана, хищники продолжают перебор жертв и возможных клеток у борта, принадлежащих их траекториям, и переходят к жертве с программой, закодированной следующим числом. Коллектив хищников отличает корректные программы от некорректных и в процессе перебора пропускает последние. В процессе такого перебора жертв любая жертва будет поймана.

В главе 5 приведено полное решение задачи преследования коллективом хищников независимой системы жертв в ¿-квадрате. Аналог теоремы 2 не имеет места в семействе квадратов произвольного размера. Неверен и результат, подобный результату теоремы 1 о невозможности поимки системы жертв. Показано, что для любой независимой системы жертв существует коллектив хищников, ловящий ее при любом начальном расположении жертв в квадрате любого размера.. В то же время для любого коллектива хищников существует размер квадрата, такой, что для любого расположения хищников в этом квадрате существует независимая система жертв,

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

Теорема 3. Имеют место следующие утверждения

1) Для любой конечной независимой системы жертв S = S(R, V — 1) существует коллектив хищников K(R,V), который, для любого натурального I, стартуя из любого канонического расположения в L^l), ловит систему жертв S при любом их начальном расположении в L^l).

2) Для любого конечного коллектива хищников K(R, V) существует натуральное число I, такое, что для любого начального расположения хищников в L${1), существуют независимая система жертв 5(1,1) и их начальное расположение в L^Q), при котором все они убегают от хищников.

Эта теорема имеет место вследствие периодичности движения в квадрате любых систем автоматов.

Для доказательства первого утверждения строится коллектив из двух автоматов-хищников, ловящих заранее заданную систему жертв. Хищники медленно обходят квадрат со стороной I, стоя в каждой клетке время const-•12. Константа подобрана так, что время, которое один из автоматов стоит неподвижно в произвольной клетке, превосходит период движения каждой жертвы, что и обеспечивает поимку.

Второе утверждение имеет место вследствие того, что трактории хищников также периодические. Обозначим период движения всего коллектива хищников в квадрате как Г, а предпериод - как Т0. Понятно, что коллектив хищников, перемещающихся в квадрате за время т способен увидить не более чем const ■ т клеток, где могут находиться жертвы. Пусть некоторая жертва в какой-то момент времени находилась на безопасном расстоянии от всех хищников. При достаточно большом размере квадрата для этой жертвы существует порядка т2 клеток, куда она бы могла переместиться за время т. Показано, что число несамопересекающихся траекторий для жертвы втечение г тактов (т.е. без повторения клеток за эти г тактов) настолько велико, что жищники не успевают обнаружить жертву на каждой из этих траекторий. Таким образом, для жертвы существует траектория, безопасная в течении т тактов при некотором т и соответствующем размере квадрата. Повторив это построение, можно построить жертв, которые будут перемещаться, не попадая в зону видимости хищников 2т тактов, Зт тактов,..., и.т.д. Можно построить жертву, которая будет перемещаться г ■ т тактов, не попадая в зону обзора хищников, где г • г > Tq+Т, причем в некоторый такт j >То + Т сама жертва находится в той же клетке, в которой уже находилась в начале периода коллектива хищников. Дальнейшая

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

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

Благодарности

Автор выражает глубокую благодарность своему научному руководителю академику В. Б. Кудрявцеву за постановку задачи и постоянное внимание к ней, В.Е. Владиславлеву, A.B. Галатенко, Д.Н. Жуку, И.В. Кучеренко и В.С.Половникову за ряд ценных замечаний, а также коллективу кафедры математической теории интеллектуальных систем механико-математического факультета Московского государственного университета имени М. В. Ломоносова за всесторонние помощь и поддержку.

Работы по теме диссертации

[1] Н. Ю. Волков. Об автоматной модели преследования. Дискретная математика 2007, Т. 19, вып. 2., стр. 131-160.

¡2] Н.Ю. Волков. Об автоматной модели преследования в базовых плоских областях. Интеллектуальные системы 2007, Т. 11, вып. 1-4, стр. 361402.

[3] Н. Ю. Волков. Об автоматной модели преследования внутри квадрата. Интеллектуальные системы 2008, Т. 12, вып. 1-4, стр. 137-158.

[4] Н. Ю. Волков. О возможности поимки жертв в квадранте. Интеллектуальные системы 2009, Т. 13, вып. 1-4, стр. 169-236, 2009 г.

Подписано в печать 09.010 Формат 60x90 1/16. Усл. печ. л. 1,0 Тираж {00 экз. Заказ 23

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имени М. В. Ломоносова

1. Введение

1.1. История вопроса.

1.2. Краткое содержание работы.

1.2.1. Постановка задачи.

1.2.2. Основные результаты.

1.2.3. Структура диссертации.

2. Основные определения и вспомогательные понятия

2.1. Формальная постановка задачи.

2.1.1. Лабиринты, в которых происходит преследование

2.1.2. Взаимодействие автоматов

2.1.3. Рассматриваемые проблемы.

2.2. Вспомогательные понятия.

2.2.1. Вспомогательные определения.

2.2.2. Композиции автоматов

2.2.3. Построение вспомогательных автоматов.

3. Преследование независимой системой хищников жертв

3.1. Траектории автомата в исследуемых лабиринтах.

3.2. Невозможность поимки жертв независимой системой хищников на плоскости.

4. Преследование коллективом хищников жертв в бесконечных лабиринтах

4.1. Поимка автоматов-жертв с периодическим поведением

4.1.1. Леммы о перемещении автоматов.

4.1.2. Вычисление коллективом автоматов арифметических функций от параметров, заданных расстановкой автоматов

4.1.3. Доказательство возможности поимки жертв с периодическим поведением

4.2. Поимка автоматов-жертв с непериодическим поведением

4.2.1. Леммы о перемещении автоматов в квадранте

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

4.2.3. Вычисление параметров жертвы по ее коду

4.2.4. Доказательство возможности поимки непериодических жертв в квадранте.

4.3. Доказательство основной теоремы.

5. Преследование коллективом хищников жертв внутри квадрата

5.1. Поимка данной системы автоматов-жертв.

5.2. Построение автоматов-жертв, убегающих от данного коллектива хищников.

5.3. Доказательство теоремы о преследовании внутри квадрата

1.1. История вопроса

Автоматный подход к решению задачи преследования впервые был применен в 1987 г. В. И. Грунской в работе [5]. В этой работе рассматривается взаимодействие двух конечных автоматов W и Z («хищника» и «жертвы») в шахматных лабиринтах, имеющих вид квадрата со стороной I. Две клетки такого лабиринта считаются соседними, если они имеют общую сторону. Каждый из автоматов W и Z способен обозревать клетки, соседние той, в которой он находится (все такие клетки, вместе с клеткой в которой на-ходрттся сам этот автомат, образуют его зону обзора). В зависимости от состояния своей зоны обзора (т.е. от наличия и расположения в зоне обзора клеток границы квадрата и от наличия и расположения в зоне обзора автомата-противника), хищник и жертва могут перемещаться за один такт в одну из соседних клеток, либо стоять на месте. Хищник и жертва делают ходы поочередно. Считается, что хищник поймал жертву, если ohpi оказались в соседних клетках.

При фиксированном произвольном размере I стороны квадрата, в котором происходит преследование, изучаются два вопроса.

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

2. Существует ли универсальный автомат-хищник W, ловящий любую жертву Z в данном лабиринте при при произвольных начальных расположениях W и Z?

На эти вопросы в работе [5] получены следующие ответы. Установлено, что для любых l,n е N существует W с числом состояний 0(п • Z2), который ловит за время 0(п ■ 14) любой автомат-жертву Z с числом состояний не большим п, в квадрате со стороной, не большей при любом начальном расположении W и Z. Установлено, что не существует автомата W, ловящего любой Z в произвольном квадрате с фиксированной длиной стороны 1,1 >8.