Стратегiї планування рiшень, Детальна інформація

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

(снують вузли чотирьох тип(в:

GOAL - вузли, як( зображують ц(л(, що можуть бути досягнут(;

PHANTOM - вузли, як( зображують ц(л(, що вже досягнут(;

1, ступ(нь виходу >1 ( зображують розгалуження часткового упорядкування;

1 ( зображують з((днання п(дплан(в в часткове упорядкування.

Кожному вузлу надаються два списки: доповнень та виключень. Вони м(стять символ(чн( вираження, описуючи зм(ни в ситуац((, що визван( д(ями, в(дпов(дними даному вузлу.

Розглянемо, наприклад, мережу, що зображу( ((рарх(ю план(в фарбування стел( ( фарбування драбини [5]. Абстрактно цей план може бути зображений одним вузлом, як показано на мал. 6, а. Б(льш докладний план ( кон(юнкц((ю двох д(й (мал. 6, б). Ще б(льш докладн( плани мали би бути: “В(ЗЬМИ ФАРБУ; В(ЗЬМИ ДРАБИНУ; ПОФАРБУЙ СТЕЛЮ;” ( “В(ЗЬМИ ФАРБУ; ПОФАРБУЙ ДРАБИНУ;”, як показано на мал. 6, в.

В систем( NOAH використову(ться стратег(я ((рарх(чного нел(н(йного планування. Ця стратег(я моделю( б(льш детальний план, моделюючи кожний вузол плану по черз(. Моделювання (розширення) вузла поляга( в застосуванн( ST-оператора, який ( моделлю д((, в(дпов(дной даному вузлу. При цьому до мереж( додаються нов( вузли з б(льш детальними д(ями ( зм(ню(ться модель ситуац(( з урахуванням впливу цих д(й. Таким чином, при моделюванн( плана утворю(ться новий б(льш детальний план.

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

Для того, щоб зобезпечити коректн(сть нового б(льш докладного плана, стратег(я NOAH використову( множину PF-оператор(в коректност(. Ц( оператори зд(йснюють глобальний перегляд плану ( накладають додатков( обмеження для л(кв(дац(( суперечностей.

Алгоритм( що зд(йсню( стратег(ю NOAH, склада(ться з таких крок(в:

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

Застосування PF-оператор(в коректност( до нового плану, що зд(йснюють необх(дне переупорядкування ( виключення надм(рних ST-оператор(в.

Перех(д до кроку 1.

Процес планування продовжу(ться доти, поки вже не знаходяться н(як( нов( детал(.

Серед PF-оператор(в коректност( вид(ляються так( оператори: усунення конфл(кт(в; використання (снуючих об((кт(в; усунення надм(рних попередник(в.

Оператор усунення конфл(кт(в використову( стратег(чний прийом “ор((нтац(я на непорушн( п(дц(л(“. Процедура, що реал(зу( оператор, розгляда( списки доповнень ( виключень кожного вузла у кон(юктивних г(лках плану. Якщо д(я в одному кон(юктивному п(дплан( вилуча( вираз, який ( попередником для п(дц(л( у другому кон(юктивному п(дплан(, виника( конфл(кт. Наприклад, план фарбування на мал. 6,в м(стить конфл(кт, тому що д(я “ПОФАРБУВАТИ ДРАБИНУ” вилуча( вираз “ПОФАРБУВАТИ СТЕЛЮ”, який знаходиться в списку доповнень вузла “ВЗЯТИ ДРАБИНУ”, попередника вузла “ПОФАРБУВАТИ СТЕЛЮ”. Конфл(кт познача(ться знаком “+” над попередньою д((ю чи знаком “-” над кроком, який його порушу(. Конфл(кт може бути розв(язаний шляхом введення обмеження, щоб п(дц(ль, яка ставиться п(д сумн(в (“ПОФАРБУВАТИ СТЕЛЮ”), досягалася ран(ш виконання порушуючого крока (“ПОФАРБУВАТИ ДРАБИНУ”) (мал. 6, г).

Под(бний конфл(кт зустр(ча(ться, якщо д(я в одн(й кон(юктивн(й г(лц( вилуча( вираз, який ( попередником для наступной п(дц(л(. В цьому випадку попередня д(я повинна бути виконана знов п(сля вилучающ(( д((.

Процедура, що реал(зу( оператор використання (снуючих об((кт(в, з(ясову(, коли неконкретний об((кт може бути ототожнений з деяким вже згадуваним в план( конкретним об((ктом, ( зд(йсню( це ототожнення. Цей оператор дозволя( вилучити вузли типу JOINT з р(зних частин плану, що призводить до переупорядкування або частково( л(неаризац((.

Процедура, що реал(зу( оператор вилучення надм(рних ST-оператор(в, розп(зна( надм(рн(сть плана (наприклад, таку, як д(я “В(ЗЬМИ ФАРБУ” (див. мал. 6, г)) ( вилуча( надм(рних попередник(в, щоб зберегти пам(ять ( запоб(гти додаткового планування на б(льш детальних р(внях.

( навпаки, в вигляд( вузл(в типу PHANTOM з в(дпов(дними списками вилучень ( доповнень за рахунок ST-оператор(в типу SEND ( RECEIVE. Досто(нством ц((( стратег(( ( розпаралелювання процеса планування, вадою - необх(дн(сть частих (нформац(йних обм(нов, що може призвести до значно( втрати ефективност( при р(шенн( задач з сильнозв(язаними п(дц(лями.

Подальший розвиток стратег(( NOAH застосовно до планування в умовах обмеження часу був виконан в [7] з реал(зац((ю в систем( DEVICER. Для зображення обмежень часу по тривалост( та старту для ц(льових умов, под(й та д(й використовуються конструкц((, аналог(чн( до конструкц(й мови SITPLAN-2.Окр(м д(й та под(й (що спрацьовують при певних умовах) паралельн( плани в DEVICER можуть м(стити виведення та запропонован( под(( (як( ( повн(стю поза контролем планувальника).

Стратег(я планування в DEVICER м(стить так( PF-оператори:

розширення вузла;

зв(язування вузл(в;

коректност(.

Зв(язування вузл(в поляга( в наведенн( зв(язку в(д ц(льового вузла T до вузла G, якщо деякий вираз вузла G досягаються (снуючим вузлом E в план(, включаючи стартовий вузол. Конфл(кти розв(язуються через упорядкування вузл(в, як( не були упорядкован( ран(ш.

Кр(м тих, що вже описан(, до складу оператор(в коректност( входять оператори звуження стартових (нтервал(в для д(яльност( (д(й, под(й, виведень, запропонованих под(й), а також оператори визначення тривалост( д(яльност( через значення зм(нних, що входять до (х опис(в. Для кожного PF-оператора може бути дек(лька точок вибору. В цьому випадку одна альтернативна вибира(ться( а (нш( збер(гаються. Якщо планувальник заходить в глуий кут, в(н поверта(ться до останньо( точки вибору ( перев(ря( (ншу альтернативу.

При плануванн( без врахування обмежень часу кожна ц(льова умова входить в певний ц(льовий вузол, який ( попередн(м до j-го вузла. Це не годиться для досягнення групи ц(льових умов, зв(язаних вкупу загальним стартовим (нтервалом ( д(яльн(стю. В DEVICER (снують окрем( “кишеньков(“ вузли для кожно( зв(язки ц(льових умов. PACK-вузол м(стить (нформац(ю про стартовий (нтервал (START) ( д(яльн(сть, пов(язану з ц(льовими умовами.