Робототехника.Фу, Ли, Гонсалес (962794), страница 93
Текст из файла (страница 93)
Целевой ППФ является (Зв) НВ(з) Чтобы показать, что обезьяна может достать бананы, эту задачу можно решить как доказательство теоремы [216). 10,5. АНАЛИЗ КОНЕЧНЫХ ЗНАЧЕНИИ наз Выше мы рассмотрели несколько методов поиска впер ад, но для конкретной задачи должно быть выбрано одно из двух возможных направлений. Однако для решения задачи часто применяется поиск в двух направлениях.
Такая смешанная стратегия давала бы возможность решить основные части задачи методом поиска вперед. Затем можно было бы идти назад, чтобы решить вспомогательные задачи, возникаю сое ин д ненни вместе отдельных частей решения. Это можно осщ ть, применяя метод анализ конечных значений.
М естви т можно осуетод у екушим и цеосновывается на установлении различия между тек левым состояниями. Если различие установлено, необходимо найти оператор, который может его уменьшить. Возможно, что этот оператор неприменим к текушему состоянию. Поэтому воз- лза никает подзадача получения состояния, в котором он может применяться. Также возможно, что оператор не приводит точно к целевому состоянию, Тогда мы имеем вторую подзадачу получения состояния, применив к которому данный оператор, мы перейдем в целевое состояние, Если различие определено правильно и результат применения оператора действительно уменыпает это различие, легче решить две подзадачи, чем исходную задачу.
Анализ конечных значений рекурсивно применяется к подзадачам. С этой точки зрения анализ конечных значений можно было бы рассматривать как метод сведения задачи к подзадачам. Для того чтобы нацелить систему на решение больших задач, различиям должны быть присвоены приоритетные уровни. Различия с высоким приоритетом рассматриваются раньше, чем различия с низким приоритетом. Наиболее важной структурой данных, используемой в анализе конечных значений, является «цель».
Цель представляет собой кодировку текушей проблемной ситуации, желаемой ситуации и историю прежних попыток преврашения текущей ситуации в желаемую. Имеются цели трех основных типов: Тип 1. Преобразование объекта А в объект В. Тип 2. Уменьшение различия между объектом А и объектом В посредством модификации объекта А. Тип З.Применение оператора О к объекту А. Для достижения целей указанных типов имеются соответствуюшие процедуры (рис, 10.11), которые могут быть интерпретированы как операторы сведения исходной задачи к подзадачам, соответствуюшим И-вершинам (в случае преобразования объекта или применения оператора) либо ИЛИ-вершинам (в случае уменьшения различия).
Первой программой, применяющей анализ конечных значений, был общий решатель задач ОРЗ (цепега! ргоЫегп зо1чег), Причиной его создания послужило частое использование этого метода для решения задач. Для ОРЗ исходной задачей является достижение цели преобразования объекта А в объект В, где А является исходным объектом или состоянием, а  — желаемым объектом или целевым состоянием. ОРЗ прекрашает работу, если для цели преобразование объекта нет различия между А и В или же для цели применение оператора оператор О непосредственно переводит А в В, Для цели уменьшение различия процесс вычисления может завершиться астаповом в ситуациях, когда нельзя применить ни один из имеюшихся операторов.
При преобразовании объекта А в объекте В для обнаружения различия между двумя объектами используется процесс сравнения. В первую очередь уменьшаются различия с более высокими приоритетами. Операторы, соответствующие уменьшению каждого различия, заносятся в таблицу различие — оператор, 537 где: РСВН (ОВ1, ЕОС) — переместить объект ОВУ в положение ЕОС; САййт (ОВУ, ЕОС) — переместить объект ОВ1 в положение ЕОС; (в'АЕК (ЕОС) — переместить роаот в положение ЕОС; РУСКЮР (ОВУ) — поднять объект ОВУ) РИТООЖН (ОВУ) — опустить оаъект ОВ11 РЕ.4СЕ (ОВП, ОВУ2) — размествть объект ОВУ1 на объекте ОВУ2, Утверждения в предуславиях и результатах действия операторов имешт следушший смысл; 1 АТ (йОВОТ, ОВУ) 2.
АТ (ОВУ, 1 ОС) 3. АТ (йО ВОТ, 1.0С) 4. АТ (йовот, ОВУ2) 3. 1.АйаЕ (ОВУ) 6. ВМАЕЕ (ОВУ) 7 СЕЕАй (ОВУ) 8. НАНОЕМРТУ 9, КОНЕ 10. Н01 ОУНО (ОВУ) 11. НОЕВ!Но (ОВП) 12, ОН (ОВУ1, ОВУ2) В таблице на рис. 10.12 отмечены случаи применения тел нли иных операторов, Заметим, что иногда могут использовзтьс» Оператор Рззлп»пе Рптооюн РЕАСВ Р)СКОР Н'АЕК Рози САННУ Прслуслозпя Оператор Результат 1.
Ат (йовот, ову) л елйае (овП Л СЕЕАй (ОВУ) Л НАНОЕМРТУ АТ (ОВУ, ЕОС) л Ат (йовот, 1.00) изв <~вй, с с~ САййг (ОВУ, ЕОС) 2 АТ (йОВОТ, ОВ1) л Вмлее (овП 3, ване 4 АТ (йОВОТ ОВУ) б ИОЕО!На (ОВ1) АТ (ОВУ, 10С) Л АТ (йОВОТ, ЕОС) гу'АеК (еос) РУСКиР (ОВУ) Рнтоои'н (овП всвс (савв О~во АТ (йОВОТ ЕОС) НОЕВ!На (ОВУ) НО!О!На (ОВУ) Ой (ОВП, ОВ12) Рнс. !0.12, Таблица кразлнчие — оператор». несколько операторов, которые уменьшают данное различие, или же один оператор может уменьшать несколько различий, Предположим, что робот должен перенести платформу с двумя объектами на ней из одной комнаты в другу)о.
Объекты на платформе также можно передвигать, Основным различием 6 АТ (йОВОТ, ОВУ2) л НОУ 01йа (О В!1) 539 бзз Рнс. 10.11. Методы анализа конечных значенвй. Рассмотрим простую задачу, операторы для решения которой приводятся ниже: Переместить объект в определенное положение Переместить робот в определенное положен не Снять один объект с другого объекта Положить одни объект на другой Освободить схват обота от объекта ержать объект в схвате робота Робо~ йовот и объект ОВ1 в одном месте Ооъект ОВ1 в месте ЕОС Робот йОВОТ в месте ЕОС Робот йОВОТ и абьект ОВУ2 в одном места Объект ОВУ большой Объект ОВУ маленький На объекте ОВУ нет другого объекта В схвате робота нет объекта Оператор не имеет предусловий В схвате робота находится объект ОВУ В схвате робота объект ОВУ1 Ооъект ОВУ1 на объекте ОВУ2 между начальным и целевым состояниями является расположение платформы.
Для уменьшения различия можно выбрать оператор Р118Н или САКЯт'. Если сначала выбирается оператор САВКУ, следует определить его предусловие. Это приводит к двум различиям, которые должны быть уменьшены, а именно: расположение робота и размер платформы, Расположение робота можно изменить с помощью оператора )ЧАЬК, но нет операторов, которые могли бы изменить размер объекта, (платформы), поэтому этот вариант оказывается тупиковым.
Рассмотрим другой вариант, т. е. попытаемся применить оператор РВСН. Он имеет три предусловия, два из которых определяют различия между начальным и целевым состояниями. Поскольку платформа предполагается большой, ни одно из предусловий не создает различия. Робот можно перевести в требуемое положение оператором ЮАЬК, и поверхность платформы можно освободить, применяя дважды оператор Р1СКЫР. Но после первого применения оператора Р1СК()Р попытка применить его второй раз приводит к другому различию: схват должен быть свободным. Для уменьшения этого различия можно использовать оператор РЫТРОЮМ. Применение оператора Р()СН почти приводит к целевому состоянию.
Объекты должны быть вновь размещены на платформе. Это осуществляется с помощью оператора Р1.АСЕ. Но он не может применяться непосредственно. Должно быть устранено другое различие, поскольку робот должен взять объекты, Это осуществляется с помощью оператора Р1СК(ЗР.
Чтобы применить оператор Р1СКЫР, робот должен находиться в месте расположения объектов. Это различие можно уменьшить, применив оператор ЮАЬК. Поскольку робот находится в месте расположения двух объектов, можно воспользоваться операторами Р1СКБР и САДКУ для передвижения объектов в другую ком. нату. Очень важен порядок рассмотрения различий; например, в первую очередь должны быть уменьшены наиболее существенные различия. В разд.
10.6 описана система ЯТК1Р8, предназначенная для решения задач роботом и используюгцая анализ конечных значений. 10.6. РЕШЕНИЕ ЗАДАЧИ Самая простая система для составления плана решения задачи роботом — производящая система, построенная на основе описания состояния в виде базы данных. Описание состояний и целей для задачи, решаемой роботом, может быть составлено из логических утверждений, В качестве примера рассмотрим схват робота и конфигурацию объектов, показанных на 540 рис. 10.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
