Робототехника.Фу, Ли, Гонсалес (962794), страница 90
Текст из файла (страница 90)
На первый взгляд эти два пути не кажутся наиболее короткими. Однако более подробное исследование показывает, что если передвигать вдоль них объект из целевого состояния, то могкно избежать двух вращений за счет несколько большего расстояния. 1 ! 1 1 ,т 1 1 -- — ~- — -1- — -л ! ! ! ! 1 .1' г Задача <Обезьяна и бананы», В комнате находятся обезьяна '1, ящик и гроздь бананов (рис. !0.7). Бананы подвешены под потолком вне досягаемости обезьяны. Каким образом обезьяна может достать бананы? Для описания состояния воспользуемся списком иа 4-х элементов (В', х, У, 2), где 1Р' — горизонтальное положение обезьяны; х =! или 0 в зависимости от тога, находится обезьяна на вершине ящика или нет соответственно; У вЂ” горизонтальное положение ящика; о Подразумевается, что обезьяной может быть моонаьмыи рооос.
рид4бвх свс рг Рис. 10.7, Задача «Обезьяна и бананы», 521 г = 1 или О в зависимости от того, достала обезьяна бананы или нет соответственно. Операторы для решения этой задачи — следующие: 1) йо10((1), Обезьяна двигается к горизонтальному положению У, или в форме производящего правила, (%', О, У, г) — — (У, О, У, з). Таким образом, состояние ()Р',О, У,г) может быть преобразовано в состояние (С, О, у, г) с помощью оператора 0010((/). 2) рцзЬЬох(Р'). Обезьяна двигает ящик к горизонтальному положению 1/, или (»,ь,», ) ' ' (г,с,г,а. Из левой части производящего правила следует, что оператор рпзЬЬох(У) может быть применен, если обезьяна расположена в том же положении В', что и ящик, но не на ящике.
Такое условие, наложенное на область применения оператора, называется аредусаовием (предпосылкой) производящего правила. 3) с!ппЬЬох. Обезьяна залезает на ящик, или ((с', О, (Р, з)» (1(г, 1, )с', 2). Необходимо отметить, что для применения оператора сВгпЬЬох обезьяна должна быть в том же положении йГ, что и ящик, но не на ящике. 4) пгазр. Обезьяна захватывает бананы, или (С, !, С, О) » (С, 1, С, 1), где С вЂ” положение на полу непосредственно под бананами. Следует отметить, что для применения оператора пгазр обезьяна и ящик должны быть в положении С, причем обезьяна предварительно должна находиться на ящике.
Рис. 10.8. Представление задачи «Обезьяна н бананы» н виде графа. Подразумевается, что как область допустимых значений, так и результаты действия операторов описываются с помощью производящих правил. Например, в правиле 2 оператор ризЬЬох()г) применяется только тогда, когда выполнено его предусловие. В результате действия этого оператора обезьяна передвинула ящик в положение )т. При такой постановке ряд целевых состояний описывается одним списком, последний элемент которого есть 1.
Пусть начальное состояние (А,О,В,О). Единственным оператором, который можно применить, является йо10(У). Он приводит к следующему состоянию (К О, В, О). Теперь применимы 3 оператора: до1о(С), рпзЬЬох()г) н с1!п1ЬЬох (если с! = В). Продолжая применять все возможные операторы к каждолву состоянию, мы создадим граф пространства состояний, показан- ный на рис. 10.8.
Нетрудно видеть, что последовательность операторов, преобразующих начальное состояние в целевое, состоит из до!о(В), рцзЬЬох(С), с1ппЬЬох и дгазр. !0.2.2. Методы поиска иа графе Для небольших графов, один из которых показан на рис. 10.8, путь из начального состояния в конечное может быть легко найден непосредственной проверкой, В случае более сложных графов для определения пути в пространстве состояний из начального состояния в конечное требуется формализованный процесс поиска.
Один из способов описания процесса поиска пути на графе заключается в использовании >троизводяи!их систем. Производяшая система включает следующее: !. Базу данных, которая содержит информацию, относяшуюся к определенной задаче. 2. Набор >гравил, действующих над базой данных.
Каждое правило состоит из левой части, которая определяет применимость правила (предусловие), и правой части, описывающей действие, которое должно быть выполнено в случае применения правила. Применение правил изменяет базу данных. 3, Стратегию управления, которая определяет, какие правила должны быть применены, а также прекращение вычислений, когда для базы данных выполняется конечное условие. На языке производящих систем граф, показанный на рис. 10.8, создается стратегией управления.
Различные базы данных, полученные с помошью правил, на графе обычно представляются в виде вершин. Таким образом, стратегия управления поиском на графе подразумевает нахождение пути на графе из начальной вершины, представляюшей собой начальную базу данных, в целевую вершину. Целевая вершина в свою очередь является базой данных, удовлетворяюшей конечному (или целевому) условию производящей системы.
Процедура поиска на графе может быть описана следующим обр зом; й '. аг 1. Создать граф поиска 6, состоящий только из начальной вершины в. Занести з в список, называемый ОРЕМ, Шаг 2. Создать список, называемый С!.ОЗЕР, который первоначально является пустым. Шаг 3. МООР: если ОРЕМ пуст, выход на аварийный останов. Шаг 4. Выбрать первую вершину яз ОРЕМ, удалить ее из ОРЕХ и занести ее в С10ЗЕР. Назвать эту вершину п. Шаг б.
Если и является целевой вершиной, выход на останов с выдачей решения, полученного с помощью отслеживания пути, помеченного указателями, в направлении о> и к з в 6 (указатели '> определяются на шаге 7). '> В данном случае под указа>~лен понимается направление дуги от одной вершины графа к другой. — Прим. перев.
Шаг О. Расширить вершину и, создав набор М из преемников, не являющихся предшественниками и. Определить вершины набора М в качестве преемников и в 6. Шаг 7. Установить указатели в направлении и от тех вершин набора М, которые еше не были в списках ОРЕХ или С) ОЗЕР. Добавить эти вершины из набора М в ОРЕМ. Для каждой вершины набора М; который уже был в ОРЕХ или СЕОЗЕР, решить, надо ли восстановить его указатель в направлении и. Для каждой вершины из М, уже находяшейся в С) ОЗЕР, определить для каждого из его потомков в 6, следует ли восстанавливать его указатель». Шаг 8.
Переупорядочить список ОРЕМ по некоторому произвольному критерию или эвристическому правилу. Шаг 9. Перейти к выполнению шага 3. Если никакая эвристическая информация не используется при упорядочении вершин из списка ОРЕХ, на шаге 8 должен быть применен некоторый произвольный критерий. Результируюшая процедура поиска называется слепой.
Первый тип процедуры слепого поиска упорядочивает вершины в ОРЕМ по мере возрастания глубины пх расположения в дереве поиска'>. Такой поиск называется поиском в ширину первого типа. Было показано, что этот метод обеспечивает нахождение пути минимальной длины к целевой вершине при условии, что этот путь существует. Второй тип слепого поиска упорядочивает вершины в ОРЕХ по мере уменьшения глубины их расположения в дереве поиска. Вершины, располагаюшиеся на наибольшей глубине, заносятся в список первыми. Вершины равной глубины располагаются в произвольном порядке.
1-!азовем этот метод поиском в глубину первого типа. Для предотврашения процесса поиска вдоль некоторого бесполезного пути устанавливается ограничение иа глубину. Ни одна вершина, глубина которой превышает ограничения, не порождается. Описанных выше методов слепого поиска достаточно для нахождения путей от начальной вершины к целевой. Во многих случаях допустимо использование дополнительной информации, зависящей от вида решаемой задачи и помогающей сократить поиск. Этот класс процедур поиска называется эвристикамп '> Есле граф, подлежащий исследованию, является деревом, то ни один из преемников, созданных на шаге 6, не был создан ранее.
Таким образом, вершины из набора М уже не входят либо в ОРЕХ, либо в СЬО5ЕО. В атом случае каждая вершина из набора М добавляется в ОРЕХ и размещается в исследуемом дереве в качестве преемника я. Если граф, подлежащий исследова ни>о, не является деревом, возможно, что некоторые из вершин набора М >'же быти созданы, т. е онн могли уже быть в ОРЕХ клв ОЕО5ЕР. з> Для обеспечения наиболее раннего завершения целевые вершины должны быть занесены в начало ОРЕМ.
бзз или наилу«шим поиском первого типа, а используемая информация, зависящая от вида решаемой задачи, называется эвристи«вской информацией. На шаге 8 процедуры поиска нз графе эвристическая информация может быть использована для упорядочивания вершин в списке ОРЕМ тзк, чтобы поиск осуществлялся среди наиболее перспективных секторов графа. Рассмотрим важный метод, который использует функцию оценивания для вычисления «перспективы» вершин. Вершины в списке ОРЕМ упорядочиваются по мере увеличения значения функции оценивзния. Связи среди вершин устанавливаются произвольно, но всегда в пользу целевых вершин. Результаты поиска существенно зависят от выбора функции оценивания. Полезный алгоритм наилучшего поиска первого типа, так называемый А*-алгоритм, приводится ниже.
Пусть функция оценивания для любой вершины и имеет следующий вид: 1 (н) = к (н) + Ь (н), где д(н) — мера стоимости прохода от начальной вершины к вершине п, а 6(н) — оценка стоимости прохода от вершины н к целевой вершине. Таким образом, 1(а) представляет собой оценку стоимости прохода от начальной вершины к целевой вдоль пути, проходяшего через вершину и.
А*-алгоритм Шаг 1. Вначале список ОРЕМ содержит только начальную вершину. Присвоить д значение О, й — произвольное значение, а 1 — присвоить значение А+ О или 6. Список СЬОЯЕР считать пустым. Шаг 2. До тех пор, пока целевая вершина не будет найдена, повторять следующую процедуру: если в списке ОРЕМ нет ни одной вершины, выдать сообщение об аварийном останове. В противном случае выбрать из ОРЕМ вершину с наименьшим значением 1.
Присвоить ей имя ВЕЗТМОРЕ (наилучшая вершина), удалить из списка ОРЕМ и занести в список СЕОЯЕР. Проверить, является ли ВЕЯТМОРЕ целевой вершиной Если да, то выход нз останов с сообщением о решении (либо выдать целевую вершину ВЕЯТМОРЕ, либо путь между начальной вершиной и целевой вершиной ВЕЯТМОРЕ). В противном случае создать вершины — преемники вершине ВЕЯТМОРЕ, но не определять указатели между вершиной ВЕВТМОРЕ и вершинами-преемниками. (Сначала необходимо установить, имеются ли среди них ранее созданные вершины.) Для каждой такой вершины, имеюшей имя 81)ССЕЯЯОК (преемиик), выполнить следуюшее: а) Установить указатель от вершины 81)ССЕЬЬОК к ВЕЬТМОРЕ. Такие обратные связи дают возможное.ь восстановить путь в случае нахождения решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
