Робототехника.Фу, Ли, Гонсалес (962794), страница 92
Текст из файла (страница 92)
АО*-алгоритм Шаг 1. В 6 входит только одна вершина, соответствуюшая начальному состоянию. (Назовем эту вершину 1Х1Т,) Вычисляетсяя й (1Х1Т) . Шаг 2. До тех пор пока 1Х1Т не будет помечена как ВОЕЧЕР илп значение й(!Х!Т) не превзойдет ЕУТН.!ТУ, повторять следующие действия; а) Идти из вершины 1Х1Т вдоль помеченных дуг и выбрать для процесса расширения одну из вершин на этом пути, ранее не подвергавшуюся расширению.
Назвать выбранную вершину ХОРЕ. б) Создать преемников вершины ХОРЕ. Если их нет, присвоить ЕЬТП.)ТУ и й значение ХОРЕ. Это означает, что ХОРЕ не является решаемой вершиной. Если преемники имеются для каждого нз них (названного ЗЦССЕ550К), который также не является предшественником ХОРЕ, делать следующее: !) добавить ЬЦССЕЬ50К к О; 2) если 3()ССЕ530К является конечной вершиной, пометить его 30ЕЧЕР и присвоить его значению й значение О; ззо 3) Если Я)ССЕ380К не является конечной вершиной, вычислить его значение й. в) Распространять вновь полученную информацию по графу следуюшим образом; Пусть 5 является набором вершин, которые были помечены 50!ЧЕР или значения й которых были изменены. И поэтому необходимо знать значения й вершин нх предшественников.
Начнем рассмотрение 5 с вершины ХОРЕ. До тех пор пока 5 не станет пустым, повторять следуюшие действия: 1) Выбрать нз 5 вершину, у которой ни один из потомков, входящих в 6, не входит в 5. ( Другими словами, надо удостовериться, что для каждой вершины, подлежащей обработке, она будет обработана раныпе любого из ее предшественников,) Назовем эту вершину С()ККЕХТ н устраним ее из 5. 2) Вычислить стоимость каждой дуги, выходящей нз СЦККЕХТ. Стоимость дуги равна сумме значений й каждой вершины на конце дуги плюс стоимость самой дуги. Присвоить новому значению й вершины СЦККЕХТ минимальное значение среди только что вычисленных стоимостей дуг, выходящих из нее. 3) Отметить лучший путь из вершины СЦККЕХТ, пометив дугу, которая имеет минимальную стоимость, вычисленную на предыдушем шаге, 4) Пометить вершину СБККЕХТЗОЕЧЕР,если всевершины, связанные с ней через вновь помеченную дугу, были помечены 501 ЧЕР.
5) Если СУККЕХТ уже была отмечена 501.ЧЕР или если стоимость вершины СЦККЕХТ только что была изменена, добавляем к 5 всех предшественников вершины СЦККЕХТ. Отметим, что вместо двух списков ОРЕХ н СЕОЬЕР, котор ые были использованы в А'-алгоритме, в АО*-алгоритме применяется единая структура 6. Эта структура представляет собой часть графа поиска, которая к этому времени уже была создана.
Каждая вершина на графе указывает как вниз (на своих преемников), так и вверх (на своих непосредственны.: предшественников). Каждой вершине графа присвоено значение й для оценивання стоимости пути от нее самой к набору вершин-решений. Значение д (стоимость прохода от начальной вершины к текушей) не сохраняется как в А'-алгоритме, поскольку й служит оценкой качества вершины. Величина Г!)Т!!.1ТУ необходима. Если оцениваемая стоимость решения становится больше, чем значение ЕЦТИ!ТУ, поиск прекрашается.
Значение РЦТП !ТУ должно быть выбрано так, чтобы соответствовать порогу, за пределами которого любое решение, даже если бы оно могло быть найдено, было бы слишком громоздким, чтобы его можно было применять на практике. Алгоритм поиска в ширину первого типа может быть получен из АО'-алгоритма, если й =— О. зз! 10.4. ПРИМЕНЕНИЕ ЛОГИКИ ПРЕДИКАТОВ Для решения задач, связанных с управлением робота, должна быть реализована возможность представления исправления и преобразования наборов утверждений. Для этого может быть использован язык логики или, более точно, язык логики предикатов первого порядка.
Логический формализм представляется привлекательным, поскольку является мощным средством выведения новых знаний из старых (методом математической дедукции). По этому методу новое утверждение истинно, если можно доказать, что оно следует из утверждения, о котором уже известно, что оно истинно. Эту идею доказательства, можно применять для получения ответов на вопросы и решения задач в робототехнике о. сп Рассмотрим сначала возможности логики высказываний ка пособа представления знаний. Она имеет то преимущество, что к ее аппарат достаточно прост н для представления знаний имеются соответствующие операции, На языке логики высказываний легко описывать явления окружающего мира в виде набора правильно построенных формул (ППФ), Например: Идет дождь.
кА1г[111Сз Светит солнце. 3111»ХУ Стелется туман. Е ОССзУ Если идет дождь, то не светит солнце. кА11»1ысз -ь 311ММУ Используя эти утверждения, мы, например, можем вывести, что не светит солнце, если идет дождь. Но очень быстро мы сталкиваемся с ограничениями логики высказываний. Предположим, мы хотим на ее языке представить очевидный факт, констатируемый следующим предположением: ДЖОН вЂ” человек Мы можем написать .[ОН[х[МА[ч[ Но аналогично можно сказать Пол — человек или РА[)[.МА[к[ 31 сз Читателям, не знакомым с логикой высказывания и логинов предикатов, мы мажем рекомендовать просмотреть введение в логику прежде, чем читать оставипюся часть главы. Читатели, желаюцгне более полно ознакомитьси с материалом мого раздела, должны просмотреть книгу [431. 532 что могло бы быть совершенно другим утверждением и нам было бы трудно вывести какое-либо заключение о степени схожести между Джоном и Полом.
Было бы намного лучше представить это в виде: МАгч([ОНХ) МА[к[(РАН-) поскольку теперь структура представления отражает структуру самих знаний. Возникает еще больше трудностей, если мы попытаемся на языке логики высказываний описать следующее утверждение: «все люди смертны», так как потребуются утверждения для представления соотношений количества, если мы не собираемся по отдельности описывать смерть каждого известного человека, Поэтому придется воспользоваться аппаратом логики предикатов, поскольку на ее языке можно описывать события, не поддающиеся описанию на языке логики высказываний. На языке логики предикатов можно представить события окружающего мира в виде ППФ. Но главная причина выбора логики предикатов состоит в том, что с ее помощью можно не только представить знания, но и получить из них новые знания, В этом разделе мы кратко опишем язык и методы логики предикатов.
Основными компонентами языка логини предикатов являются: прсдигсатьц переменные, функции и константы. Предикаты используются для установления связи в рассуждениях. Например, для описания факта «Робот в комнате г|» достаточно простой формульыатолса; 1[к[РООМ(РОБОТ, г,) В этой формуле РОВОТ и гг являются константами. Обычно формулы-атомы состоят из предикатов и термов. Константа является простейшим видом терма для представления объектов или вещей при рассуждениях. Переменные также являются термами для описания объектов, относящихся к некоторому классу, как, например, [г[РООМ(х,у). Функции применяются для определения связей между объектами, подлежащими рассмотрению. Например, функция пзо(пег (мать) применяется для установления связи между человеком и его (ее) родителем по материнской линии.
Можно воспользоваться следующей формулой-ато. мом для представления утверждения «Мать Джона замужем за отцом Джона»: МАР Р[Е[3[[з[йег(10Н[ч[), шо[[тег(3О[[[х[)), Формула-атом имеет значение И (истина), когда соответствующее утверждение истинно, и Л (ложь), когда соответствующее утверждение ложно.
Таким образом 1[к[РООМ(РО. 533 ВОТ, г,) имеет значение И, а !Ь()1ООМ((1ОВОТ, гз) имеет значение Л. Формулы-атомы являются элементарными формулами, из которых строятся более сложные утвержления на языке логики предикатов. Из формул-атомов можно строить более сложные ППФ, применяя операции Л (и) '/ (или) и =»- (следование). Формулы, построенные путем связи одних формул с другими символом Л, называются конъюнкциями, а символом х/ — дизъюнкциями, Символ =>- применяется для представленим утверждения «если — тогда». Например, «если обезьяна на ящике, она схватит бананы».
ОЫ(МОЬ(КЕУ, ВОХ) =» 61(АБР(МОЫ КЕУ, ВАЫАЫАЯ). Символ — означает отрицание, т. е. он изменяет значение ППФ с И на Л и наоборот. (Истинное) утверждение «робот не находится в комнате гз» может быть представлено в виде — ! Ы РООМ(1(О ВОТ, г,) Иногда формула-атом Р(х) имеет значение И для всех возможных значений х, Это свойство описывается с помошью кван- тора всеобшности (Чх), который ставится перед Р(х). Если Р(х) имеет значение И хотя бы для одного значения х, это свойство представляется с помошью квантора существования (Зх), который ставится перед Р(х). Например, утверждение «все ро. боты серые» можно выразить в виде (7х) ((1 ОВОТ (х) —.~ СО 1.0(1(х, ОМФАУ)), а «в комнате г, находится объект» (Вх) 1Ь(цООМ (х,г,) Если Р и Я являются ППФ, истинные значения выражений, составленных из этих формул, приводятся ниже в таблице: И Л И л и И Л Л И И И Л Л И Л и И Л Л л И И Л И Если два истинных значения ППФ одинаково интерпрети.
руются, эти ППФ являются эквивалентными, Используя таблицу истинных значений, мы можем установить следующие эквивалентности: — ( — Р) эквивалентно Р Р '/ Я эквивалентно — Р =» Я О':яВОХ АТ(ВОХ, В) АТ(ВАЬ1АЬ(АБ; С) — 11В 3аконы де Моргана (р',/ (з) эквиватентно Р Л Я : (Р Л а) эквивалентно - Р '/ — а дистрибутивные законы: Р Л(Я Ч Р) эквивалентно (Р Л Я)'/(Р/' )() Р'I (11 Л )т) эквивалентно (Р'/ Я)Л(Р" й) Коммутативные законы: Р Л Я эквивалентно (,1Л Р Р '/ 1,! эквивалентно („! '/ Р Ассоциативные законы: (Р Л Я)'/ Я эквивалентно Р Л Я Л Р) (Р'„/ Я)~/ Р эквивалентно Р',l(Я'/Я) Контропозитивный закон: Р =:. Я эквивалентно О ~ — Р И кроме того мы имеем. — (Зх) Р(х) эквивалентно (1/х) ( Р(х)) — (чх)Р(х) эквивалентно (Зх) (- Р(х)) В логике предикатов м имеются правила вывода, которые ПФ ля ППФ. Важным правилом вывода является ППФ К из ППФ мод с поненс, являюшийся правилом вывода ° „, =- 11/, Д гое правило вывода — универсальная ь ППФ й/(А) из ППФ специализация позволяет выводить А .
яется константой. Используя совместно иенс и ниверсальную специализацию, можно, ца~ р- А ППФ (Ч ) ((У/ (х) =» 1Р (х)) и 1( ). К/ (А). В логике предикатов ППФ формулы, полученные с помощью п авил вывола, называю ются теоремами, а последовательность правил вывода — оказ т — д а ельством теоремы. В искусственном интеллекте некоторые д ~е задачи могут быть рассмотрены как заи вы- дачи доказательства те а теорем, Послеловательность правил вода дает решение требуемой задачи. Пример. Пространство состояний задачи «Обезьяна и оана- ны» можно описать ППФ.
Мы предполагаем, что используются Кг зр (захват), с1!п1ЬЬох (прыжок на ашик), рпэЬЬох (передвижение ящика). а ьное состояние зь описывается следуюшим паыусть начальн бором ППФ: Предикат ОЬ)ВОХ имеет значение И(истинно), только когда обезьяна находится на вершине яшика, а предикат НВ имеет значение И, только когда у обезьяны имеются бананы. Действия трех операторов можно описать следующими Г1ПФ: 1) цгазр (17з)(ОМВОХ(в) А АТ(ВОХ, С, з) =» НВ(ставр(з))) что означает: «для любого з, если обезьяна находится на ящике б и ящик расположен в точке С в состоянии в, обезьяна завладеет ананами, если оператор цгазр применить к состоянию в». Отметим, что значением оператора цгазр(з) является новое состояние после того, как этот оператор был применен к состоянию в. 2) с1ппЬЬох ( !7з) (ОМВОХ(с1!шЬЬох (в))) что означает: «для любого з обезьяна будет находиться на ящике в состоянии, которое получается в результате применения оператора с1!шЬЬох к состоянию з», 3) рцзЬЬох (Ъх)гз) (- ОМВОХ(з) =»АТ(ВОХ, х, рцзЬЬох(х, з))) не находится что означает: «для любого х и з, если обезьяна не н на ящике в состоянии з, ящик будет в положении х в состоянии, полученном в результате применения оператора рцзЬЪох(х) к состоянию з».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
