Intel_Nils (526801), страница 9
Текст из файла (страница 9)
Гл. 2. Представление задач в пространстве состояний Состояние, возникающее в результате применения одного из этих операторов,— это просто то состояние, которое описывается вектором (9, О„х) по истечении Ы секунд. (Во многих типичных задачах управления действия операторов могут быгь компактно представлены с помощью дифференциальных уравнений.) Критерий достижения цели. Предположим, что целевое состояние описывается вектором (О = О, 0 = О, х = 0), Тогда нам нужно найти последовательность операторов, которая будет преобразовывать любое данное состояние в целое. Конечно, такая последовательность не должна приводить ни к какому состоянию, описываемому переменными О, 0 и х, для которого неизбежно в конце концов полное нарушение работы системы (Оно происходит при 0 = ~90'.) В некоторых типичных задачах управления часто можно получить (аналитическими методами) уравнения разделяющих поверхностей„которые разбивают векторное пространство состояний на непересекающиеся области, такие, что для всех векторов иэ данной области в данный момент должно быть применено одно и то же управление (один и тот же оператор).
В этих случаях несложное вычисление можетдатьответ,который иначе получался бы с помощью поиска. Читатель должен понимать, что мы не собираемся предлагать использовать поисковые процессы в случаях, когда известны прямые методы решения. Мы хотим лишь подчеркнуть, что часто можно воспользоваться эффективными методами перебора для решения тех задач, для которых прямые методы еще не найдены. 27. ВЫБОР «ХОРОШИХ» ЛРЕДСТАВЛЕНИИ Выбор для данной задачи определенного представления в пространстве состояний существенно определяет те поисковые усилия, которые придется приложить для ее решения.
Очевидно, что предпочтительны представления с малыми пространствами состояний (т.е. такие, графы которых имеют небольшое число вершин). Существует*множество примеров задач, кажущихся трудными, но таких, что при правильной их трактовке соответствующие пространства состояний оказываются очень узкими, Подчас данное пространство состояний «сжимается в точку» после того, как обнаруживается, что некоторые операторы могут быть отброшены за ненадобностью, а другие — объединены в более мощные операторы. И даже если такие простые преобразования неосуществимы, может оказаться, что полная переформулировка задачи, изменяющая само понятие состояния, приведет к меньшему пространству. Еще слишком слабо поняты те процессы, которые необходимы для первоначального представления задач и для усо- 2.7. Выбор «хороших«представление вершенствования этих представлений.
По-видимому, желаемый прогресс в представлении задачи зависит от опыта, накопленного в попытках решить задачу в рамках данного представления. Этот опыт позволяет выделить упрощающие понятия„такие, как свойства симметрии или полезные последовательности операторов, которые следует объединить в макрооператоры. Чрезвычайно важная идея в области представлений задач связана с использованием переменных в описаниях состояний.
Тогда выражения, содержащие переменные, могут быть использованы для описания целого множества состояний, а не только одного. Подстановка каких-то частных значений (констант) вместо этих переменных в указанные выражения дает конкретные описания состояний. Выражение, содержащее переменные, которое используется для описания множества состояний в указанном смысле, называется схемой для описания состояний. Мы проиллюстрируем на примере использование схем для описания состояний.
К задаче об обезьяне и бананах часто обращаются в литературе по искусственному интеллекту при демонстрации работы автоматических решателей задач, создаваемых для осуществления умозаключений, опирающихся на здравый смысл. Задачу можно сформулировать так. В комнате, где находится обезьяна, имеются ящик и связка бананов, причем бананы подвешены к потолку настолько высоко, что обезьяна не может до них дотянуться с пола. Какая последовательность действий позволит обезьяне достать эти бананы? (Предполагается, что обезьяна должна подойти к ящику, подтащить его к бананам, забраться на него и достать бананы.) Как следует строить для этой задачи представления в пространстве состояний? В описании состояния должны непременно появиться следующие элементы: координаты обезьяны в комнате (по горизонтали и по вертикали), координаты ящика в комнате и наличие у обезьяны бананов. Эти элемеяты удобно представить в виде четырехэлементного списка (ч~, х, у, г), где те — координаты обезьяны в горизонтальной плоскости (двумерный вектор), х — это ! или О в зависимости от того, где обезьяна находится, на ящике или нет, у — координаты ящика в горизонтальной плоскости (двумерный вектор), г — это ! или О в зависимости от того, достала обезьяна бананы или нет.
Если бы каждое отдельное значение списка (», х, у, г) описывало ровно одно состояние, то мы имели бы бесконечное число состояний, поскольку число различных расположений предметов в комнате бесконечно. Мы могли бы сделать цро- 46 Гя. 2. Представление задач в пространстве состояний странство состояний конечным, допустив, что предметы могут находиться лишь в конечном числе точек (скажем, точек ре- шетки), но все же число точек, достаточное для поставленной задачи, привело бы к чрезвычайно большому пространству со- стояний. Другой путь состоит в использовании схем. Для входя- щих в схему переменных имеются частные значения (напрнмер, константы), которые должны подставляться на нх место прн применении оператора или при проверке того, что цель достиг- нута. Операторы в этой задаче соответствуют четырем возмож- ным действиям, которые могут выполняться обезьяной: 1) подойти (и) .
— обезьяна идет к точке и в плоскости пола комнаты (и — переменная), 2) передвинуть (ч) †обезья передвигает ящик а точку ч пола комнаты (ч — переменная), 3) взобраться †обезья забирается на ящик, 4) схватить — обезьяна хватает бананы. В связи с наличием переменных в «подойти», «передвинуть» эти операторы на самом деле являются схемами. Условия при- менимости и действия этих операторов даются следующими правилами переписывания: (,т.т.а " " н,о,т,н, (ъч> О, чт, 2) о (че, 1, ттт, 2), (с, 1, с, 0) -» (с, 1, с, 1), где с — координаты точки пола, расположенной непосредственно под бананами (двумерный вектор).
Применение некоторых операторов, например «передвинуть», связано с ограничением значений переменных, представляющих координаты обезьяны и ящика, от которых теперь требуется. чтобы они были одинаковыми. Мы будем считать идентичными две схемы для описания состояний, если они отличаются лишь наименованием переменных. В такой формулировке элементы множества целевых состояний описываются любыми списками, последний элемент которых есть единица. Предположим, что вначале обезьяна находится в точке а пола, а ящик — в Ь. Тогда описанием начального состояния будет (а, О, Ь, 0). Единственный оператор, который применим в этом состоянии,— это «подойти», приводящий к схеме (и, О, Ь, 0).
Теперь применимы три оператора. Если и = Ь, то обезьяна может либо забраться на ящик, либо передвинуть его, Независимо от величины и обезьяна могла бы переместиться куда-нибудь Х7. Выбор «корошик» лредставкений еще. Вчезание на ящик приводит к состоянию с описанием (Ь, 1, Ь,О); перемещение ящика в и приводит к схеме (и,О,и,О),-а переход в другое место, описываемое новой переменной, не изменяет описания. Продолжая процесс применения всех операторов, мы построим пространство состояний, иллюстрируемое графом на рис.
2.10. Мы видим, что этот граф весьма невелик и на нем легко можно найти путь, решающий нашу задачу (жирные Рис 2.!О. Граф дия задачи об обеаьяае и баиаиак. стрелки). Подставив вместо переменных их соответствующие частные значения, как это показано на рис. 2.10, мы получаем последовательность операторов: подойти (Ь), передвинуть (с), взобраться, схватить. На этом мы закончим рассмотрение вопроса о представлениях задач в пространстве состояний. Приведенные в этой главе примеры касались нескольких сторон проблемы представлений, хотя пока еще нет удовлетворительной теории представлений и изменения представлений. В следующей главе мы перейдем к гораздо.
более глубоко разработанной области приемов поиска в пространстве состояний. 48 Гл. 2. Представление задач в нространстве состояний 88. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ Составные элементы представления в пространстве состояний Три элемента, из которых слагается представление в пространстве состояний — описания состояний, операторы и критерии цели — давно считаются основными в области автоматического решения задач. Эти понятия обсуждаются в книге Эрнста и Ньюэлла (1969), в которой пассматривается программа универсального решателя задач. Более абстрактное исследование проблемы описания состояний и операторов можно найтиуАмареля (1967, 1969).
Пример использования правил переписывания для задания операторов имеется в системе для решения задач, описанной Квинлаиом и Хантом (1968). Основные элементы языка теории графов (дуги, вершины, пути и т. п.) часто используются при описании процессов решения задач. Классическими книгами по теории графов являются книги Бержа (1958) и Оре (1962). Оре (1963) написал также популярную элементарную книжку, содержащую применения теории графов к различным комбинаторным задачам, Недетерминированные программы Название недетервсинированный алгоритм было предложено Флойдом (1967а).
Флойд допускал использование в таких алгоритмах функции «выбора> для упрощения описания стратегий полного перебора. Позднее Манна (1970) описал класс программ, допускающих как недетерминированные утверждения присваивания (подобные функции выбора), так и недетерминированные операции ветвления. Он привел методику доказательства корректности (правильности) программ, содебжащих эти новые элементы. В более ранней статье Манна (1969) рассмотрел проблему доказательства корректности обычных (детерминированных) программ. Файкс (!970) описал полную систему решения задач, в которой задачи ставятся на некотором процедурном языке, допускающем использование недетерминированных функций выбора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
