Применение вероятностных автоматов

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

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

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

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

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

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

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

Пускай входная лента представляет собой протокол загруженности поперечной улицы. На входной ленте могут быть 2 символа: на поперечной улице никого нет (Пусто) и на поперечной улице имеется автотранспорт (Не пусто). Сам автомат имеет возможность находиться в 2-ух состояниях: движение по трассе открыто (на поперечной улице — перекрыто), и закрыто (открыто на поперечной улице). Обозначим эти состояния за Откр и Закр соответственно. Логично, что, если поперечная улица пуста, то автомат непременно переходит в положение Откр. Если трасса открыта, а на поперечной улице кто-то ожидает, то переходим в Закр с возможностью 30%, а в 70% случаев остаемся в Откр. Если трасса перекрыта, а автотранспорт на поперечной все еще имеется, то в половине случаев остаемся в Закр, а в половине — перейдем в Откр. (рисунок 13).

Рисунок 13. Схема автомата Посчитайте, сколько времени нужно ожидать шоферу на поперечной улице для того, чтобы проехать перекресток с возможностью не меньше 80%, если сведения снимаются раз в 2 минуты. Естественно, в редких вариантах наш автомат имеет возможность создавать длинные пробки, однако в целом он действует удовлетворительно. Мы видим, что вероятностные автоматы — неплохой метод решения фактических задач, однако у них имеется серьезный недочет: нет никакой гарантии, что путь решения будет найден за количество шагов, наименьшее заранее заданного N. Поэтому нужно, чтоб шанс нахождения решения за приемлемое количество шагов был довольно велик — это следует помнить, назначая матрице переходов значения вероятностей.

Использование вероятностного автомата в задаче поиска. Задачка розыска ставится, в частности, практически в хоть какой RРG либо аркадной системе. К сожалению, достойным методом она позволяется далеко не всегда. Чаще только употребляются совсем простые алгоритмы, которые никак не справляются с мало-мальски трудными преградами (к примеру, если «нюхач» располагаться в комнате, а цель — в коридоре за стенкой, противоположной входу, «нюхач» непременно запутается). Очевидно, есть алгоритмы поиска с полной информацией о карте, однако для корректной работы они настоятельно просят огромных баз данных. Не считая того, эти алгоритмы поиска несправедливы по отношению к человеческому игроку.

Мы постараемся построить автоматный алгоритм поиска в ортогональном лабиринте. На 1-ый взгляд задачка видится неподъемной — так как подтверждено, что поиск в графе автоматно никак не допустим. Однако когда говорят «не разрешим автоматно», предполагают, будто невозможно выстроить такой детерминированный автомат, который бы сумел постановить задачу в общем случае. Мы же будем пользоваться вероятностными автоматами.

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

Алгоритм хождения по стенке детерминирован и просто записывается в форме конечного автомата (рисунок 14).

Рисунок 14. Алгоритм автомата Разберемся, что происходит в каждом состоянии.

Состояние Вправо. Производится поворот вправо и шаг. Если успешно, то переход в Вправо, иначе переход в Вперед.

Состояние Вперед. Производится поворот влево и шаг. Ели успешно, то переход в Вправо, иначе переход в Влево.

Состояние Влево. Производится поворот влево и шаг. Если успешно, то переход в Вправо, иначе переход в Назад.

Состояние Назад. Производится поворот влево и шаг. Переход в Вправо.

Если бы наш лабиринт никак не имел круговых путей и состоял из коридоров ширины, самое наибольшее, 2, то такой стратегии было бы достаточно. Однако мы разрешаем задачку в общем случае, поэтому поглядим, как люди справляются с повторяющимися путями. Человек, который долго идет по стенке в темноте, рано или поздно решит, что нужно поменять стратегию поиска, — тут стоит отметить фразу «рано или поздно»: это прямое распоряжение на то, что стоит применять вероятностные автоматы. Здравые суждения дают подсказку, что, повернув 4 раза на 90 градусов в 1 и ту же сторону, ищущий имеет возможность предположить зацикленность маршрута. Однако в спиральном лабиринте циклов нет, но там имеется та же картина поворотов. Так как наш автомат не может расценивать расстояния, он просто не сумеет распознать спираль и круг.

Поэтому, как и человек, автомат, повернув на 360 градусов, меняет стратегию поиска не всегда, а только с некой вероятностью.

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

Ключевой эпизод в построении нашего алгоритма — отбор вероятностей на «развилках». Если сделать вероятности замены стратегии очень большими, то автомат будет обнаруживать «нетерпеливость», идя вдоль неровной стены. Если сделать их очень маленькими — растет угроза долго кружить по 1 маршруту. Легче только выбирать применимые значения «на глазок», проведя для различных вероятностей огромное количество испытаний в нескольких лабиринтах и подобрав те характеристики, для которых время поиска оказывается в целом меньше. В нашем случае успешнее только оказалась возможность замены стратегии, равная 0,2.

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

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

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