Планирование последовательности движений

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

Такой план порождается одной из следующих двух функций:

План имеет форму списка инструкций для физически существующей руки или для ее машинной модели. Это цепочки из инструкций MOVETO (ПЕРЕМЕСТИТЬСЯ-К), GRASP (ВЗЯТЬ) и UNGRASP (ОТПУСТИТЬ), подобные цепочке, порожденной в ситуации на рис. 12.1 в ответ на команду (PUT-ON В С) (ПОСТАВИТЬ В С):

Рис. 12.1. Мир робота

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

Свойство SIZE (РАЗМЕР) для блока задается шириной, глубиной и высотой. Свойство SIZE для пирамид и шаров задается размерами описанных около них блоков, как изображено на рис. 12.2. Для руки (HAND) мы имеем что-то вроде следующего.

Значения свойств для руки:

Рис. 12.2. Чтобы упростить планирование положения предмета, робот рассматривает сферы и пирамиды как бы вписанными в прямоугольные блоки

Хозяева списков свойств - функции GET и PUTPROP

Для извлечения из памяти значений свойств используется функция GET:

Для указания или замены значения некоторого свойства используется функция PUTPROP:

Заметьте, что возвращаемое функцией PUTPROP значение является как раз той величиной, которую она связывает с атомом, задаваемым в качестве первого аргумента. Полезно также знать, что функция GET возвращает NIL, если свойство с данным именем отсутствует.

Функция PROG создает переменные и обеспечивает цикл

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

Синтаксис для функции PROG проще всего объяснить на примере. Вог один из способов записать функцию для вычисления факториала числа:

Несколько моментов требуют пояснения. Нам нужно помножить n на n - 1, затем на n - 2 и так далее до 1. Это перемножение будет реализовано путем многократного обращения к фрагменту программы, расположенному сразу же за LOOP.

• Аргументами для функции PROG преимущественно служат s-выражения, которые оцениваются одно за другим. Если управление выходит за рамки функции PROG, то, как и в случае функции COND, возвращается NIL.
• Первую позицию в функции PROG всегда занимает список переменных, которые все связываются при входе в PROG, а при выходе их величины восстанавливаются к прежним значениям. Каждой из них автоматически присваивается начальное значение NIL.
• Когда в ходе вычисления функции PROG встречается функция RETURN (ВЕРНУТЬСЯ), PROG немедленно завершается. Значением такой завершенной функции PROG является значение аргумента для функции RETURN, которая остановила работу PROG.
• Всякий атом, появляющийся в качестве аргумента функции PROG, рассматривается в качестве метки в программе. Эти атомы указывают на те места, куда управление передается функциями GO. (GO (метка)) передает управление в то место программы, которое помечено атомом с именем (метка). Теперь ясно, что функция для вычисления факториала работает циклически, возвращаясь к метке LOOP, пока переменная N не станет равной нулю. Каждый раз в таком цикле RESULT (РЕЗУЛЬТАТ) изменяется путем умножения на N. Функция COND проверяет выполнение условия остановки, т. е. N=0, и выполняет функцию RETURN, когда этот тест проходит. RESULT начинает со значения NIL, как и все переменные функции PROG, но устанавливается равной 1 перед тем, как начинается цикл.

В настоящее время существует тенденция избегать использования функций GO, поскольку с ними программа часто становится плохо обозримой, а следовательно, с трудом поддается отладке. Альтернативой является функция DO, в настоящее время включенная в ряд версий языка Лисп. К сожалению, не во всех системах Лиспа встроена функция DO, но ее достаточно легко написать с помощью PROG.

Для системы, работающей с блоками, необходимы специальные функции

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

• GET-POSSIBLE-SUPPORT (ОБНАРУЖИТЬ-ВОЗМОЖНУЮ- -ОПОРУ) - функция, которая просматривает свойства, относящиеся к размерам и местоположению всех объектов, с тем чтобы определить, существует ли предмет, лежащий непосредственно под данным предметом.
• FIND-SPACE (НАЙТИ-МЕСТО)- функция, которая пытается найти место для данного предмета на данной опоре. Она работает, пытаясь применить предикат CLEARP (СВОБОДНО), в последовательности точек на поверхности опоры, выбираемой наугад. После 10 безуспешных попыток функция FIND-SPACE прекращает работу и возвращает NIL. Функция FIND-SPACE всегда сразу же возвращает NIL, если рассматриваемый предмет является пирамидой или шаром.
• TOPCENTER (ЦЕНТР, или МЕСТО-ЗАХВАТА) - функция, которая определяет, куда поместить руку, если указан блок, который нужно взять, и его местоположение.
• REPORT (ОТЧЕТ) - отладочная функция, которая распечатывает свой аргумент, а затем останавливается, позволяя пользователю исследовать значения различных величин.

Процедуры для работы с кубиками относительно прозрачны

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

Целью функции PUT-ON (ПОСТАВИТЬ-НА) является размещение одного объекта на другом. При обращении к ней делается проверка, не являются ли эти два объекта одним и тем же предметом. Если да, то выполняется отладочная функция REPORT (ОТЧЕТ), печатающая соответствующее сообщение. Обычно этого не происходит, и первая функция COND не срабатывает. Фактически работа состоит в нахождении места и последующего размещения объекта в этом месте. Если функция FIND-SPACE не может подобрать подходящего места, то предоставляется возможность действовать функции MAKE-SPACE, (ОСВОБОДИТЬ-МЕСТО). Мы увидим, что функция MAKE-SPACE является более мощной, чем FIND- SPACE, потому что она может убрать препятствия и, таким образом, создать необходимое пространство.

Рис. 12.3. В программе планирования для робота используется множество коротких целенаправленных процедур. PUT-ON (т. е. ПОСТАВИТЬ-НА) означает поставить один блок на другой. PUT-AT (т. е. ПОМЕСТИТЬ-В) означает поместить предмет в указанное место. Функция PUT-AT используется как для достижения главной цели, так и для того, чтобы помочь удалению препятствий, находящихся на блоке, который необходимо переместить, и на целевом блоке. MAKE-SPACE, (т. е. ОСВОБОДИТЬ-МЕСТО) более эффективна, чем FIND-SPACE (НАЙТИ-МЕСТО), потому что она может перемещать предметы, если иначе доступного места для объекта найти нельзя. Функции REMOVE-SUPPORT (УБРАТЬ-ОПОРУ) и ADD-SUPPORT (ДОБАВИТЬ-ОПОРУ) являются спомогательными. Функция ADD-SUPPORT отказывается дейсвовать, если поддерживающим предметом является шар или пирамида

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

Функция PUT-AT (ПОМЕСТИТЬ-В) отличается от PUT-ON тем, что ее второй аргумент является конкретной точкой в пространстве, а не именем объекта. Она реализуется непосредственно в четырех последних строках программы, которые вызывают функции GRASP (ВЗЯТЬ), MOVE-OBJ ЕСТ (ПЕРЕМЕСТИТЬ-ОБЪЕКТ) и UNGRASP (ОТПУСТИТЬ).

До того как начнут работать эти программы, однако, некоторая предварительная функция COND убеждается, что ошибок нет. Может сложиться так, что предикат CLEARP (СВОБОДНО) установит, что имеется место для данного объекта, а функция GET-POS- SIBLE-SUPPORT (ОБНАРУЖИТЬ-ВОЗМОЖНУЮ-ОПОРУ) покажет, что под предполагаемым местом что-то находится.

Обратите внимание на то, как AND (И) используется для того, чтобы объединить в одном предложении COND функции (CLEAR PLACE OBJECT) (СВОБОДНО МЕСТО ОБЪЕКТ) и (GET-POSSIBLE- SUPPORT PLACE) (ОБНАРУЖИТЬ-ВОЗМОЖНУЮ-ОПОРУ МЕСТО). Это возможно даже несмотря на то, что GET-POSSIBLE-SUPPORT не является предикатом, возвращающим Т или NIL. Очевидно, что AND, как и функция COND, ведет себя несколько несимметрично в отношении Т и NIL.

• Аргументы в AND вычисляются слева направо. Если встречается NIL, то NIL сразу же возвращается этой функцией, а остальные аргументы оставляются без внимания. В противном случае AND возвращает значение своего последнего аргумента.

Другими словами, все, что отлично от NIL, ведет себя как Т, насколько это касается логики. Это важное свойство. Функция OR (ИЛИ) ведет себя аналогично:

• Аргументы в OR вычисляются слева направо. Если встречается что-либо отличное от NIL, то эта величина немедленно возвращается функцией, а остальные аргументы игнорируются. В противном случае OR возвращает NIL. При дальнейшем углублении в описание системы может вызвать удивление сложность функций GRASP (ВЗЯТЬ), но она ответственна за целый ряд моментов:
• Во-первых, она осуществляет проверку, не находится ли тот объект, который предстоит взять, уже в руке манипулятора.
• Далее, обследуется список свойств объекта, чтобы убедиться, что свойство DIRECTLy-SUPPORTS (СЛУЖИТ-НЕПССРЕДСТ- ВЕННОЙ-ОПОРОЙ) указывает, что поверхность объекта свободна и его можно схватить рукой. Если нет, то происходит обращение к функции CLEAR-TOP (ОСВОБОДИТЬ-ПОВЕРХНОСТЬ). Если функция CLEAR-TOP отказывается выполнить свою задачу, то функция REPORT сигнализирует об ошибке.
• Наконец, может оказаться, что в настоящий момент рука манипулятора держит что-то еще, и от этого, разумеется, нужно избавиться. Функция UNGRASP (ОТПУСТИТЬ) выполнит такую задачу, если данный предмет опирается на какой-то другой предмет. В противном случае требуется функция GET-RID-OF (ИЗБАВИТЬСЯ).

После того как осуществлены соответствующие проверки и выработаны необходимые реакции, функция GRASP делает отметку, что рука держит объект, изменяя соответствующим образом свойство GRASP (ВЗЯТЬ) у руки (HAND). После этого функция GRASP передает управление функции MOVE-HAND (ПЕРЕМЕСТИТЬ- РУКУ), которая устанавливает руку в положение над тем объектом, который необходимо взять. Наконец, некоторое добавление делается в создаваемом плане с использованием функции CONS, чтобы внести элемент, отражающий действие "взять".

Мы увидим, что в этот план могут внести вклад лишь еще две функции, UNGRASP и MOVE-HAND.

После того как предмет был взят рукой, функция PUT-AT (Г10- МЕСТИТЬ-В) использует функцию MOVE-OBJECT (ПЕРЕМЕС- ТИТЬ-ОБЪЕКТ), чтобы привести его в заданное положение. Как и функция схватывания, функция MOVE-OBJECT первоначально проверяет, не выполнена ли уже эта работа. Как правило, нет, и функция MOVE-OBJECT должна заняться изменением свойства места для объекта и обновлением информации, связанной с положением руки (обращаясь к функции MOVE-HAND (Г1ЕРЕМЕС- ТИТЬ-РУКУ)). Функции REMOVE-SUPPORT (УБРАТЬ-ОПОРУ) и ADD-SUPPORT (ДОБАВИТЬ-ОПОРУ) обеспечивают обновление свойств SUPPORTED-BY (ОПИРАЕТСЯ-НА).

Функция MOVE-HAND (ПЕРЕМЕСТИТЬ-РУКУ) изменяет положение руки и вносит свой вклад в общий план.

Как в случае функции GRASP (ВЗЯТЬ), так и в случае функции UNGRASP (ОТПУСТИТЬ), при входе в функцию делается проверка, не выполнено ли уже данное действие. Это осуществляется посредством простой проверки, не находится ли что-нибудь в руке. Далее объект отпускается путем модифицирования того же самого свойства GRASPING (ДЕРЖИТ), проверкой которого мы только что занимались, а также вносится дополнение в значение переменной PLAN (ПЛАН), Заметим, однако, что эти изменения делаются лишь только, если функции UNGRASP известно, что опора имеется. Если значение свойства SUPPORTED-BY (ОПИРАЕТСЯ-НА) есть NIL, то функция UNGRASP возвращает NIL.

Функция GET-RID-OF (ИЗБАВИТЬСЯ) очень проста. Она помещает предмет на стол, найдя для него свободное место. Обратите внимание на использование PUT-AT (ПОМЕСТИТЬ-В). Этим замыкается цикл в сети функций, что придает системе существенно рекурсивный характер.

Обратимся теперь к функции CLEAR-ТОР (ОСВОБОДИТЬ-ПОВЕРХНОСТЬ). Ее задачей является удаление всех предметов, непосредственно поддерживающихся тем предметом, который предполагается взять в руки. Это достигается путем использования функции GO, образующей цикл, выполняемый до тех пор, пока каждый из объектов, указанных в свойстве DIRECTLY-SUPPORTS (СЛУЖИТ-НЕПОСРЕДСТВЕННОЙ-ОПОРОЙ), не будет помещен на стол функцией GET-RID-OF.

В функции REMOVE-SUPPORT (УБРАТЬ-ОПОРУ) используются два теста, полезные на этапе отладки, в остальном же она лишь изменяет отношения опоры, которые уже имелись в старом месте. В ней используется функция DELETE, удаляющая элементы из предъявляемого списка. Первым аргументом функции DELETE является удаляемый элемент, а вторым - тот список, из которого должен быть удален данный элемент.

Функция ADD-SUPPORT (ДОБАВИТЬ-ОПОРУ) существенно сложнее. Ее задачей является создание новых отношений поддержки, соответствующих новому положению только что перемещенного объекта. Она сообщает об отказе, однако, если для обеспечения опоры не находится ни одного объекта или если предлагаемый в качестве опоры объект не является ни блоком, ни столом. Пирамиды и шары не годятся. При неудаче в попытке изменить отношения опоры вступает в действие функция REPORT, приостанавливающая дальнейшие действия.

Функция MAKE-SPACE (ОСВОБОДИТЬ-МЕСТО) представляет собой не что иное, как многократное обращение к функции GET- RID-OF (ИЗБАВИТЬСЯ), чтобы освободить место для нового объекта. Цикл, содержащий обращения к GET-RID-OF, прерывается, как только будет расчищено достаточно пространства для того,^ чтобы свою задачу могла выполнить функция

PRINT и READ помогают функциям поддерживать связь с пользователем

Перед тем как закончить описание работы в мире кубиков, проанализируем отладочную функцию REPORT. Это нужно сделать по двум причинам. Во-первых, необходимо привлечь внимание к очень важному фактору - снабжению программ отладочными средствами. Во-вторых, необходимо ввести в рассмотрение две важные функции системы Лисп: PRINT (ПЕЧАТЬ) и READ (ЧТЕНИЕ). Без функции PRINT пользователь мог бы узнать, что делает какая-то функция системы Лисп, только когда появится ее значение. Без функции READ функция системы Лисп могла бы получить информацию лишь через свои аргументы и глобальные значения переменных. Таким образом, PRINT и READ открывают большие возможности для коммуникации. К счастью, обе они достаточно просты.

Функция PRINT находит значение своего единственного аргумента, "печатает" его на экране дисплея и возвращает Т в качестве результата. Так, следующая функция BORE-ME (СКУЧИЩЕ) будет печатать все числа подряд, пока что-нибудь не сломается:

Функция PRINT всегда в качестве значения возвращает Т:

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

Функции PRINT и READ позволяют определить REPORT:

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

Отладочные функции обычно системно-зависимы и намного более изощренны, чем простая функция REPORT, описанная здесь. Это объясняется потребностью в некотором способе обнаружения ошибок, встречающихся при оценивании результата функции READ, прежде чем они приведут к разрушению контекста, который функция REPORT пытается проанализировать.

Система, работающая в мире кубиков, имеет гетерархические свойства

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

Рис. 12.4. Большинство языков программирования диктует организацию системы, которая характеризуется небольшой глубиной процедур

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

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

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

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

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

• Функции управления распределены по системе. Модули взаимодействуют, как совокупность экспертов. Графически система скорее напоминает сеть процедур, чем структуру с главной программой и подпрограммами, вызываемыми в строго определенном и неизменном порядке. Процедуры связаны с другими процедурами посредством звеньев потенциальной передачи управления, используемых в соответствии с контекстом, который определяется совместно системой и той задачей, которая решается.
• Система является целенаправленной. Процедуры на всех уровнях весьма короткие и связаны с достижением определенных целей. Цели достигаются либо путем формулирования небольшого числа подцелей для других процедур, либо путем прямого обращения к нескольким элементарным единицам.
• Сами процедуры содержат в себе необходимую информацию для формулирования условий, при которых они способны выполнить свою работу. Это делается посредством спецификаций, расположенных в начале процедуры. Обычно достаточно простого обращения к базе данных, чтобы убедиться, что мир находится в состоянии, обеспечивающем нормальную работу процедуры, а если нет, то вызываются соответствующие предваряющие процедуры.

Моделирование осуществляется непосредственно

Здесь будет полезно взять и промоделировать на вычислительной машине те действия, которые вытекают из попытки поместить блок В на блок С в ситуации, изображенной на рис. 12.1 Полезны при этом как сами процедуры, так и линии передачи управления, показанные на рис. 12.3. Диаграмма ниже показывает результат. Отношения главный - подчиненный отображаются горизонтальными уступами, показывающими, кто вызывает кого. Порядок во времени отображен расположением по вертикали.

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

Задачи из мира кубиков - хорошая проверка методов планирования

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

Одна из известных трудных задач связана с одновременным достижением многих целей. Рис. 12.5 дает простую иллюстрацию. Блок А должен быть на блоке В и блок В должен быть на блоке С. Если этих целей добиваться в указанном порядке, то на первом шаге просто устроенной системы А будет помещено на В. Но затем, чтобы поместить В на С, необходимо снять А с В, аннулируя тем самым работу первого этапа. Для того чтобы избежать подобной ошибки, требуется более внимательный анализ совокупности одновременно поставленных целей и их подцелей.

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

Рис. 12.5. Задача состоит в том, чтобы поместить А на В и В на С. Если эти две части задачи рассматривать в неправильном порядке, то работа будет потрачена впустую