Основные определения

Комплексная схема нечеткого планирования

Особенности планирования целенаправленных действий

Оценка сложности задачи планирования

Литература

При планировании в пространстве задач ситуация несколько иная. Пространство образуется в результате введения на множестве задач отношения типа: "часть - целое", "задача - подзадача", "общий случай - частный случай" и т. п. Другими словами, пространство задач отражает декомпозицию задач на подзадачи (цели на подцели). PR-проблема состоит в поиске декомпозиции исходной задачи на подзадачи, приводящей к задачам, решение которых системе известно. Например, ИС известно, как вычисляются значения sin x и cos x для любого значения аргумента и как производится операция деления. Если ИС необходимо вычислить tg x, то решением PR-проблемы будет представление этой задачи в виде декомпозиции tgx=a =sinx/cosx (кроме л:=л/2+k л).

1. Планирование по состояниям. Представление задач в пространстве состояний предполагает задание ряда описаний: состояний, множества операторов и их воздействий на переходы между состояниями, целевых состояний. Описания состояний могут представлять собой строки символов, векторы, двухмерные массивы, деревья, списки и т. п. Операторы переводят одно состояние в другое. Иногда они представляются в виде продукций А=>В, означающих, что состояние А преобразуется в состояние В.

Пространство состояний можно представить как граф, вершины которого помечены состояниями, а дуги-операторами. Если некоторая дуга направлена от вершины n_i, к вершине n,, то п, называется дочерней, а n_j;-родительской вершинами

Последовательность вершин n_i1, n_i2, ... ,n_ik , в которой каждая n_i-дочерняя вершина для вершины n_ij-1 , /=2,..., k, называется путем длиной k от вершины n_i1, к вершине n_ik .

Таким образом, проблема поиска решения задачи <А,В> при планировании по состояниям представляется как проблема поиска на графе пути из A в B. Обычно графы не задаются, а генерируются по мере надобности.

Метод ветвей и границ. Из формирующихся в процессе поиска неоконченных путей выбирается самый короткий и продлевается на один шаг. Полученные новые неоконченные пути (их столько, сколько ветвей в данной вершине) рассматриваются наряду со старыми, и вновь продлевается на один шаг кратчайший из них. Процесс повторяется до первого достижения целевой вершины, решение запоминается. Затем из оставшихся неоконченных путей исключаются более длинные, чем законченный путь, или равные ему, а оставшиеся продлеваются по такому же алгоритму до тех пор, пока их длина меньше законченного пути. В итоге либо все неоконченные пути исключаются, либо среди них формируется законченный путь, более короткий, чем ранее полученный. Последний путь начинает играть роль эталона и т. д.

Алгоритм кратчайших путей Мура. Исходная вершина x₀ помечается числом 0. Пусть в ходе работы алгоритма на текущем шаге получено множество дочерних вершин Г(x_i) вершины x_i . Тогда из него вычеркиваются все ранее полученные вершины, оставшиеся помечаются меткой, увеличенной на единицу по сравнению с меткой вершины x_i, и от них проводятся указатели к x_i. Далее, на множестве помеченных вершин, еще не фигурирующих в качестве адресов указателей, выбирается вершина с наименьшей меткой и для нее строятся дочерние вершины. Разметка вершин повторяется до тех пор, пока не будет получена целевая вершина.

Алгоритм Харта, Нильсона и Рафаэля. В алгоритме объединены оба критерия: стоимость пути до вершины g(x) и стоимость пути от вершины h(x) - в аддитивной оценочной функции f (x) = g (x) + h (x). При условии h(x)<h_p(x), где h_p(x)- действительное расстояние до цели, алгоритм гарантирует нахождение оптимального пути.

Поиск планирования в пространстве задач заключается в последовательном сведении исходной задачи к все более простым до тех пор, пока не будут получены только элементарные задачи. Частично упорядоченная совокупность таких задач составит решение исходной задачи. Расчленение задачи на альтернативные множества подзадач удобно представлять в виде И/ИЛИ-графа. В таком графе всякая вершина, кроме концевой, имеет либо конъюнктивно связанные дочерние вершины (И-вершина), либо дизъюнктивно связанные (ИЛИ-вершина). В частном случае, при отсутствии И-вершин, имеет место граф пространства состояний. Концевые вершины являются либо заключительными (им соответствуют элементарные задачи), либо тупиковыми. Начальная вершина (корень И/ИЛИ-графа) представляет исходную задачу. Цель поиска на И/ИЛИ-графе - показать, что начальная вершина разрешима. Разрешимыми являются заключительные вершины (И-вершины), у которых разрешимы все дочерние вершины, и ИЛИ-вершины, у которых разрешима хотя бы одна дочерняя вершина. Разрешающий граф состоит из разрешимых вершин и указывает способ разрешимости начальной вершины. Наличие тупиковых вершин приводит к неразрешимым вершинам. Неразрешимыми являются тупиковые вершины, И-вершины, у которых неразрешима хотя бы одна дочерняя вершина, и ИЛИ-вершины, у которых неразрешима каждая дочерняя вершина.

Метод ключевых операторов. Пусть задана задача <А, В> и известно, что оператор f обязательно должен входить в решение этой задачи. Такой оператор называется ключевым. Пусть для применения f необходимо состояние С, а результат его применения есть f(с). Тогда И-вершина <A,В> порождает три дочерние вершины: <A, С>, <С, f(c}> и <f(с), В>, из которых средняя является элементарной задачей. К задачам <A, С> и <f(с), В> также подбираются ключевые операторы, и указанная процедура редуцирования повторяется до тех пор, пока это возможно. В итоге исходная задача <A, В> разбивается на упорядоченную совокупность подзадач, каждая из которых решается методом планирования в пространстве состояний.

анализ целей и средств и рекурсивное решение задач. В каждом цикле поиска ОРЗ решает в жесткой последовательности три типа стандартных задач: преобразовать объект A в объект В, уменьшить различие D между A и В, применить оператор f к объекту A. Решение первой задачи определяет различие D второй - подходящий оператор f, третьей - требуемое условие применения С. Если С не отличается от A, то оператор f применяется, иначе С представляется как очередная цель и цикл повторяется, начиная с задачи "преобразовать A в С". В целом стратегия ОРЗ осуществляет обратный поиск - от заданной цели В к требуемому средству ее достижения С, используя редукцию исходной задачи <A, В> к задачам <A, С> и <С, В>.

Метод иерархической системы продукций решателя ABSTRIPS . В этом методе разбиение пространства поиска на уровни иерархии осуществляется с помощью детализации продукций, используемых в методе STRIPS. Для этого каждой литере ППФ, входящей в множество Р условий применения продукции, присваивается вес j, j=0, k, и на i-м уровне планирования, осуществляемом методом системы STRIPS, учитываются лишь литеры веса j. Таким образом, на k-ом уровне продукции описываются наименее детально, на нулевом-наиболее детально как в методе системы STRIPS. Подобное разбиение позволяет для планирования на j-м уровне использовать решение (j+1)-го уровня как скелет решения j-го уровня, что повышает эффективность поиска в целом.

Схемой SS-проблемы называется пара M=(S,G), где S-множество состояний, G-множество отображений g: S->S, называемых операторами. Путем из состояния s₀эS в состояние s_rэS называется конечная последовательность p=(( s₀, , g₀), (s₁, g₁),...,(s_k-1, g_k-1) s_k ) , такая, что g_iO s_i= s_i+1 для i=0,..., k-1. SS-проблема-это четверка Р=(S, G, i ,f), где (S, G)-схема SS-проблемы, i, fэS-соответственно начальное и заключительное состояние. Путь х, ведущий из i в f, есть решение Р, а множество всех подобных путей составляет множество решений.

Схемой PR-проблемы называется пара .N=(S , Г), где S -множество проблем, Г-множество отображений g : S ->S ⁺, называемых операторами. Если РэS , p эS ⁺, то g _р(p )-отображение, представляющее проблему Р в виде цепочки подпроблем p =P1...Pn. Для схемы N= (S , Г) накрывающий путь q из проблемы s ₀ в конечное множество проблем S _k= {s ₁,..., s _n}э _S ^| является конечной последовательностью, где q= ((x₀ , y₀), (x₁, y₁),..., (x_k-1, y_k-1), x_k), x_i э S ⁺ для i=0,...,k, yэГ⁺ для i=0,..., k-1, так что x₀=s ₀, x_kэS ⁺_k. PR-проблема представляет собой четверку Z=(S , Г, Ро, Ф), где (S , Г)-схема PR-проблемы, Р_оэS -начальная проблема, ФМ S -множество конечных проблем. Решение Z представляет собой накрывающий путь (S , Г) из Р_о в Ф^/_xМ Ф, множество решений x_z, есть множество всех решений Z.

Импликата проблемы Р есть пара (p , y ), где p =P_iP₂... P_k - цепочка проблем, y -отображение из Х_р1 C Х_р2 ... C Х_рk в Х_р( Х_рi обозначает

множество решений Р_i<). Импликативная схема есть тройка L =(Р, p , y ), такая, что Р - проблема, (p , y ) - импликата Р. Множество Т импликативных схем называется импликативной сетью. Множество проблем импликативной сети

W _t={x|($ L )((L =(Р, p , y ))L ((х=Р)\/(х- символ p ))}.

Объединим синтаксис и семантику подхода, основанного на разбиении проблемы на подпроблемы. PR-проблема Z=(S , Г, Ро, Ф) представляет импликативную сеть Т тогда и только тогда, когда S =W _t и для каждого L =(Р, p , y )эT существует в точности одно g эГ, такое, что Рg =p , и для каждого g эГ, и для каждого Р из области определения g существует в точности одно L =(Р, p , Y )' T, такое,что p =Pg Проблема Р решена тогда и только тогда, когда Х_p- непустое множество.

Если PR-проблема представляет импликативную сеть, то проблема Р₀ разрешима. Для существования решения достаточно, чтобы импликативные схемы в импликативной сети Т существовали только для всех пар (xi, у,),i=0,..., k-1, входящих в накрывающий путь схемы PR-проблемы. В этом случае синтаксис и семантика PR-проблемы не совпадают. В данном случае PR-проблема частично представляет импликативную сеть Т.

Рассмотрим понятие, объединяющее подходы разбиения проблемы на под-проблемы и поиска в пространстве состояний. 1-проблемой (объединенной проблемой) называется четверка R=(B, Г, Р₀, Т), где В-множество SS-проблем;

(В, Г)-схема PR-проблем; Р₀эB -основная проблема;T-импликативная сеть, такая, что W _TЗ B© Ж . Кроме того, R есть решение SS-проблемы Р₀. Учитывая связь между существованием импликативной сети и разрешимостью проблемы, легко показать, что если для заданной I-проблемы найден накрывающий путь х из Р₀ на множество Ф'Н В, проблемы Ф' разрешимы как SS-проблемы, если х частично представляет импликативную сеть Т, то и проблема R разрешима как SS-проблема.

Рассмотрим головоломку "Ханойская башня" . Имеются три стержня 1, 2 и 3 и три диска различных размеров А, В, С с отверстием в центре, которые могут одеваться на стержни. В исходной позиции диски находятся на стержне 1; самый большой диск С-внизу, самый маленький диск А- наверху. Требуется перенести все диски на стержень 3, перемещая за один раз только один диск. Брать можно только самый верхний диск на стержне, причем его нельзя класть на диск, меньший по размерам. Используем для записи состояний и операторов классическую формализацию. Выражение ijk обозначает конфигурацию, при которой диск С находится на стержне i, диск В - на стержне j и диск А-на стержне k. Выражение xij обозначает действие, при котором диск х перемещается со стержня i на стержень j. С помощью этого формализма можно просто записать все состояния и переходы головоломки в виде треугольного графа, где вершины соответствуют расположению дисков на стержнях, а дуги-возможным перекладываниям дисков (рис.1). На этой головоломке легко проиллюстрировать все основные понятия обобщенной стратегии проблем.

Представим головоломку в виде модели I-проблемы. Рассмотрим I-проблему R=(B, Г, P₀T), где B={Р₀, P₁,...,P₉}; Г={g }; T=={L ₁,L ₂,L ₃}. SS-проблемы Р₀,P_1...,P₉ определяются следующим образом. На рис. 1 показана схема SS-проблемы M==(S, G), где

Схема PR-проблемы N= (В, Г) приведена на рис. 2; импликативная сеть Т- на рис.3, причем L ₁=(P₀, P₁Р₂Р₃, Y ), L ₂= (P₁, P₄P₅P₆, Y ), L з== (Р₃, P₇P₈P₉,Y ), где Y (x₁,x₂,x₃)=x₁x₂x₃.

Проблемы Р₂ и P₄-P₉ решаются перекладыванием одного диска и являются элементарными. Проблемы P₁ и Р₃ решаются с помощью манипуляций только с дисками В и А и являются более простыми, чем Р₀. Проблемы P₁ и Р₃ решаются, а проблема Р₀ сводится к P₁, P₂ и Р₃ аналогичной манипуляцией с дисками, синтаксис которой выражен оператором g , а семантика - отображением Y .

Нечеткой SS-проблемой назовем SS-проблему, у которой i , f-нечеткие множества, операторы g эG-нечеткие матрицы, a -решением нечеткой SS-проблемы называется путь g=g₁...g_n,g_iэG,i=1,...,n, такой, что iOg₁O... ... Og_nOf? a , где О - максимальное произведение нечетких матриц.

Нечеткой PR-проблемой называется PR-проблема, у которой элементам g эГ приписывается степень принадлежности m g (p )э[0,1], a -решением нечеткой PR-проблемы называется решение PR-проблемы, для которой ming _{ij? a} ,g _ij эy_i.

Накрывающий путь в этом случае называется накрывающим a -путем. Степень принадлежности m g ( p ) интерпретируется как степень возможности разбиения проблемы на подпроблемы.

Нечеткой импликативной схемой называется импликативная схема, все отображения Y которой имеют степень принадлежности m Y ₍(p )э[0,1]. Степень принадлежности интерпретируется как возможность получения решения проблемы из решений соответствующих подпроблем. Нечеткой импликативной сетью называется импликативная сеть с нечеткими импликативными схемами.Нечеткая PR-проблема представляет нечеткую импликативную сеть, если кроме обычных условий для импликативной сети выполняется неравенство m Y (p )? m g (p ) ? a ,

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

Аналогично определяется нечеткая I-проблема. Но построить a -решение нечеткой PR-проблемы по a -решениям ее нечетких подпроблем можно лишь в частных случаях и при наложении дополнительных условий. Пусть задана нечеткая PR-проблема, где S -нечеткие SS-проблемы, и существует простейшее a -решение Z,

т.е.такое p э S ⁺,что m g _{p ? a} ,и если p =P₁..P_n,то все проблемы P_{i a} -разрешимы,

где P_i=(S_i,G_i,J_i,F_i ).a -решение проблемы P₀ существует при m Y (p )? m g (p )? a для импликативной сети.Запишем более конструктивное условие для этого.Пусть для всех i оператор g_i есть a -путь решения проблемы P_iи F_i=J_i+1.Тогда,если выполняется

max m [F_nЗ (F_n-1З (...F_1З (J o g₁)o g₂)...)o g_n)]? a

и g=g₁...g_n,то g- a -решение SS-проблемы P₀.

Пусть задан некоторый предметный мир, в котором действие ИС состоит в достижении целевых ситуаций s_k из некоторых исходных ситуаций s_n c помощью планов действий;V=bi1...b_in,где bi-исполнительный модуль из данного набора В₀. Задать ситуацию s в таком мире-это значит указать свойства с_iО С предметов а_kО A₀ и отношения между ними r_pО R₀, которые имели, имеют или будут иметь место в момент t. Модель предметного мира для такого действия ИС можно представить в виде Mо=<Aо, Во, Со, Ro>, а задачу планирования действий в мире Мо следующим образом: заданы исходная s_n и целевая s_k" ситуации, необходимо построить из исполнительных модулей b_iО Во план действий V, который, будучи примененным к Sn, позволяет достичь Sk.

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

Пусть C₁ - множество, получаемое огрублением свойств сО С₀ , В₁ - множество элементарных задач, получаемое переименованием исполнительных модулей b_iО B₀, A_{1 ?} A и R_1? Ro. Тогда модель мира тактических задач можно представить в виде Mo=<A₁, B₁, C₁, R₁>, постановку тактической задачи р-

в виде пары <s_n, s_k >, а ее решение-в виде совокупности V = Ь₁ , ..., Ь_in. Очевидно, благодаря указанному огрублению в мире M₁ становятся неразличимыми отдельные состояния предметов и исполнительных модулей. Однако подобное упрощение, вызываемое "грубостью" органов чувств ИС, еще не позволяет значительно снизить размерность пространства поиска решений V, поэтому необходимо дальнейшее обобщение M₁ уже на понятийном уровне.

В мире M₁ тактические ситуации s описываются, как и ситуации s в мире M₀, через свойства объектов и отношения между ними. Однако такие описания не носят целостного характера, так как не содержат в явном виде смысловых структур. Выявление таких обобщенных структур, а также формирование соответствующих им тактических ситуаций s осуществляются на основе понятий, которыми располагает ИС, и означают осмысливание ею сложившихся или целевых ситуаций s с точки зрения этих понятий, используемых в этом случае как программы-тесты. Таким образом, в мире M₂ указанные ситуации s представляются в виде укрупненных предметов a_{k О} A₂, свойства которых c_{i О} C₂ и отношения r_{2 О} R₂ между которыми, как и сами укрупненные предметы, определяются понятиями-тестами. Аналогично обстоят дела и с решениями V в мире M₁. Целостное описание V означает описание этих решений именно как типовых задач. Таким образом, в мире M₂ имеют место типовые задачи b_{i О} B₂.

1. Анализ вычислительных задач оказывается PSPACE-полной проблемой даже при условии, что "пустых" величин W нет .

2. Для вычислительных моделей без функциональных величин, т. е. с пустыми D_b и F, проблема анализа вычислительных задач оказывается: а) PSPACE-полной для Н, содержащих функциональные и операторные зависимости без W ; б) NP-полной для Н, содержащих только функциональные и вариантные зависимости без "пустой" величины W ; в) полиномиальной (по времени работы планировщика) для Н, содержащих только функциональные и неявные зависимости; г) можно построить планировщики с линейным временем работы для Н только с функциональными зависимостями без W и для Н с функциональными и неявными зависимостями .

В системе ПГИЗ D_b и F пусты, а в Н имеются только функциональные и операторные зависимости без "пустой" величины W . В системе автоматического синтеза программ СПОРА используется исчисление предикатов, для которого разработана специальная стратегия вывода .

Функциональной зависимости (F->Y₁), где F -функциональная величина типа (X->-Y), предполагающей предварительный синтез процедуры вычисления F, входными параметрами которой являются величины из списка X.

Операторных зависимостей, предполагающих синтез т процедур с входами "условиями подзадач" X₁, Х₂, ..., Х_ь-

Вариантных зависимостей, предполагающих, что создаются две ветви вычислений: для первой известны значения всех величин из списка Y₁, для второй - из списка У₂.

Рассмотрим простой (но типичный) пример. Пусть имеют место функциональная зависимость D₁: (A, В, СR Е) и операторные зависимости D₂: ((СR Е ) R Е₁), D₃:(( BR Е₁)_)R Е₂)), D₄: ((AR Е₂ ) R Е₃). Необходимо найти Ез. Для этого следует решить подзадачу (AR Е₂ ). Если воспользоваться зависимостью D₃, то придем к поиску решения новой подзадачи ( BR Е₁). Если использовать зависимость D₂, то придем к необходимости решения подзадачи ( CR Е), которая согласно D₁ разрешима только тогда, когда A и В известны. Степень взаимодействия подзадач в этом примере равна трем. Процесс является типичной схемой планирования в пространстве задач .

Для планировщиков, работающих в "исчислении вычислительных задач;", синтез решения вычислительной задачи происходит за время hq^rl/r!, где h - константа, l-длина записи задачи, определяемая как суммарное число вхождений имен используемых величин в F и H, q- общее число "различных" аргументов величин из "условия подзадач" в операторных зависимостях из H и "условий вариантов" в вариантных зависимостях из H, r-минимальная степень взаимодействия подзадач в исходной задаче . Эта оценка носит квазиоптимальный характер. Планировщик работает долго только на тех задачах, которые не являются естественными, так как требуют предельного переплетения между собой всех подзадач, на которые разбивается исходная задача. Эксперименты показывают, что для задач, встречающихся на практике, время работы планировщика является полиномиальным. Память, необходимая для работы планировщика в "исчислении вычислительных задач", оценивается величиной bl², где Ь - константа. Если в Н нет вариантных зависимостей, то требуется линейный объем памяти dl, где d-константа .

В известных сейчас планировщиках получаемые программы далеки от оптимальных. Наблюдается тенденция ухудшения качества программ при уменьшении времени работы планировщика. При этом синтезировать оптимальные последовательные программы труднее, чем оптимальные параллельные программы. Это обстоятельство в связи с развитием ЭВМ новой архитектуры, ориентированной на параллельные процессы, может оказаться выгодным. Например, задача поиска минимальных по времени последовательного исполнения программ для решения вычислительных задач, у которых D_b пусто, а Н состоит только из функциональных зависимостей W , оказывается NP-полной в сильном смысле . С другой стороны, в "исчислении вычислительных задач" при условии, что D_b пусто, а Н состоит из функциональных и неявных зависимостей, можно за линейное время kl (k - константа) синтезировать программу, параллельное выполнение которой требует минимального для данной задачи времени .

Предельно неконструктивная; вычислительная задача считается разрешимой, если в любой базе данных (любой интерпретации), удовлетворяющей всем ограничениям вычислительной модели, имеет место некоторая функция типа (XR Y);

предельно конструктивная: обобщенная стандартная схема программы считается решением вычислительной задачи, если в любой интерпретации, удовлетворяющей всем ограничениям вычислительной модели, имеет место функция типа (XR Y), вычисляемая программой П, получающейся из обобщенной стандартной схемы программы соответствующей конкретизацией предикатных и функциональных символов.

1. Аверкин А.Н. и др. .Обобщенные стратегии в решателях проблем.
2. Диковский А.Я. , Канович М.И. . Вычислительные модели с разделяемыми подзадачами.
3. Ефимов Е.И. Решатели интеллектуальных задач.
4. Эрлих А.И. . Диалоговая система моделирования альтернатив и выбора решений в проектировании / Представление знаний в человеко-машинных и робото-технических системах.
5. Файкс Р, Нильсон Н. . Система STRIPS - новый подход к применению доказательства при решении задач / / Интегральные роботы.
6. Ньюэлл А. Эмпирические исследования машин "Логик-теоретик": пример изучения эвристики.