WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Стратегiї планування рiшень - Реферат

Стратегiї планування рiшень - Реферат

моделюваннi плана утворюється новий бiльш детальний план.
Особистий пiдплан для кожного вузла буде правильним, але немає гарантiї, що буде правильним план вцiлому, через можливi взаємодiї мiж новими докладними кроками. Наприклад, розширення, що входять в план на мал. 6, в при уточненнi плану на мал. 6, б, роблять загальний план некоректним, тому що вони передбачають фарбування драбини ранiш фарбування стелi.
Для того, щоб зобезпечити коректнiсть нового бiльш докладного плана, стратегiя NOAH використовує множину PF-операторiв коректностi. Цi оператори здiйснюють глобальний перегляд плану i накладають додатковi обмеження для лiквiдацiї суперечностей.
Алгоритмє що здiйснює стратегiю NOAH, складається з таких крокiв:
1. Моделювання бiльш детального плану в семантичнiй мережi, що призводить до нового бiльш докладного плану.
2. Застосування PF-операторiв коректностi до нового плану, що здiйснюють необхiдне переупорядкування i виключення надмiрних ST-операторiв.
3. Перехiд до кроку 1.
Процес планування продовжується доти, поки вже не знаходяться нiякi новi деталi.
Серед PF-операторiв коректностi видiляються такi оператори: усунення конфлiктiв; використання iснуючих об'єктiв; усунення надмiрних попередникiв.
Оператор усунення конфлiктiв використовує стратегiчний прийом "орiєнтацiя на непорушнi пiдцiлi". Процедура, що реалiзує оператор, розглядає списки доповнень i виключень кожного вузла у кон'юктивних гiлках плану. Якщо дiя в одному кон'юктивному пiдпланi вилучає вираз, який є попередником для пiдцiлi у другому кон'юктивному пiдпланi, виникає конфлiкт. Наприклад, план фарбування на мал. 6,в мiстить конфлiкт, тому що дiя "ПОФАРБУВАТИ ДРАБИНУ" вилучає вираз "ПОФАРБУВАТИ СТЕЛЮ", який знаходиться в списку доповнень вузла "ВЗЯТИ ДРАБИНУ", попередника вузла "ПОФАРБУВАТИ СТЕЛЮ". Конфлiкт позначається знаком "+" над попередньою дiєю чи знаком "-" над кроком, який його порушує. Конфлiкт може бути розв'язаний шляхом введення обмеження, щоб пiдцiль, яка ставиться пiд сумнiв ("ПОФАРБУВАТИ СТЕЛЮ"), досягалася ранiш виконання порушуючого крока ("ПОФАРБУВАТИ ДРАБИНУ") (мал. 6, г).
Подiбний конфлiкт зустрiчається, якщо дiя в однiй кон'юктивнiй гiлцi вилучає вираз, який є попередником для наступной пiдцiлi. В цьому випадку попередня дiя повинна бути виконана знов пiсля вилучающiї дiї.
Процедура, що реалiзує оператор використання iснуючих об'єктiв, з'ясовує, коли неконкретний об'єкт може бути ототожнений з деяким вже згадуваним в планi конкретним об'єктом, i здiйснює це ототожнення. Цей оператор дозволяє вилучити вузли типу JOINT з рiзних частин плану, що призводить до переупорядкування або часткової лiнеаризацiї.
Процедура, що реалiзує оператор вилучення надмiрних ST-операторiв, розпiзнає надмiрнiсть плана (наприклад, таку, як дiя "ВІЗЬМИ ФАРБУ" (див. мал. 6, г)) i вилучає надмiрних попередникiв, щоб зберегти пам'ять i запобiгти додаткового планування на бiльш детальних рiвнях.
Розвиток стратегiї NOAH застосовно до системи з двох кооперуючих планувальникiв (процесорiв) був описаний в [8]. У вiдповiдностi з цiєю стратегiєю кон'юктивна цiль розподiляється мiж процесорами i , кожний з яких реалiзує стратегiю NOAH. Пiдплани, що генерує процесор , вiдображуються в семантичнiй сiтцi процесора i навпаки, в виглядi вузлiв типу PHANTOM з вiдповiдними списками вилучень i доповнень за рахунок ST-операторiв типу SEND i RECEIVE. Достоїнством цiєї стратегiї є розпаралелювання процеса планування, вадою - необхiднiсть частих iнформацiйних обмiнов, що може призвести до значної втрати ефективностi при рiшеннi задач з сильнозв'язаними пiдцiлями.
Подальший розвиток стратегiї NOAH застосовно до планування в умовах обмеження часу був виконан в [7] з реалiзацiєю в системi DEVICER. Для зображення обмежень часу по тривалостi та старту для цiльових умов, подiй та дiй використовуються конструкцiї, аналогiчнi до конструкцiй мови SITPLAN-2.Окрiм дiй та подiй (що спрацьовують при певних умовах) паралельнi плани в DEVICER можуть мiстити виведення та запропонованi подiї (якi є повнiстю поза контролем планувальника).
Стратегiя планування в DEVICER мiстить такi PF-оператори:
" розширення вузла;
" зв'язування вузлiв;
" коректностi.
Зв'язування вузлiв полягає в наведеннi зв'язку вiд цiльового вузла T до вузла G, якщо деякий вираз вузла G досягаються iснуючим вузлом E в планi, включаючи стартовийвузол. Конфлiкти розв'язуються через упорядкування вузлiв, якi не були упорядкованi ранiш.
Крiм тих, що вже описанi, до складу операторiв коректностi входять оператори звуження стартових iнтервалiв для дiяльностi (дiй, подiй, виведень, запропонованих подiй), а також оператори визначення тривалостi дiяльностi через значення змiнних, що входять до їх описiв. Для кожного PF-оператора може бути декiлька точок вибору. В цьому випадку одна альтернативна вибираєтьсяє а iншi зберiгаються. Якщо планувальник заходить в глуий кут, вiн повертається до останньої точки вибору i перевiряє iншу альтернативу.
При плануваннi без врахування обмежень часу кожна цiльова умова входить в певний цiльовий вузол, який є попереднiм до j-го вузла. Це не годиться для досягнення групи цiльових умов, зв'язаних вкупу загальним стартовим iнтервалом i дiяльнiстю. В DEVICER iснують окремi "кишеньковi" вузли для кожної зв'язки цiльових умов. PACK-вузол мiстить iнформацiю про стартовий iнтервал (START) i дiяльнiсть, пов'язану з цiльовими умовами.
На мал. 7 зображена мережа для таких цiльових умов:
GOAL: A; 'START BEFORE 15 300 'DUR 1000 (B; C) 'DUR INFINITY D .
Процедури, якi реалiзують оператор усунення конфлiктiв, повиннi турбуватися , щоб умови кожного кишенькового вузла зберiгалися на протязi певного часу. Наприклад, будь-яка дiяльнiсть, що суперечить А (мал. 7), повинна бути упорядкована чи пiсля вузла 3, чи перед вузлом 4.
Кожна дiяльнiсть в семантичнiй мережi плану також має стартовий iнтервал. За умовчанням цей iнтервал є ( - початок планування).
Стартовий iнтервал цiльового вузла визначається з опису цiлi. В процесi планування нижня (EST) i верхня (LST) межi стартового iнтервала дiяльностi можуть бути пiдданi ревiзiї процедурою, що реалiзує PF-оператори звуження стартового iнтервалу. Стартовий iнтервал нiколи не розширюється, за винятком тих випадкiв, коли робиться вiдступ назад. Стартовi iнтервали двох послiдовних вузлiв в мережi плану є залежними.
Припустимо, - послiдовнi вузли, а - тривалiсть .
Тодi необхiдно виконати такi нерiвностi:
Оскiльки iнтервал дiяльностi не може бути розширений, якщо перша нерiвнiсть не виконується, ми можемо лише збiльшувати . Якщо друга нерiвнiсть не виконується, ми можемо лише зменшити . В усiх випадках необхiдно зберегти нерiвнiсть
Зазначенi нерiвностi складають основу процедури, що реалiзує оператор звуження стартових iнтервалiв.
Кожний раз, коли вузли зв'язуються, розширюються або упорядковуються для розв'язання конфлiктiв, стартовi iнтервали цих вузлiв повиннi бути перевiренi та сжатi так, щоб зберегти умови нерiвностей.
Коли цiльовий вузол розширюється в дiяльнiсть, яка має особистий стартовий iнтервал, цi два iнтервали повиннi бути узгодженi, якщо це можливо, а якщо нi - розширення повинне бути проiгноровано. Межi цiльового iнтервалу завжди будуть числовi. Якщо обидвi межi дiяльностi також будуть числовi, ми просто беремо максимум двох нижнiх i максимум двох верхнiх меж. Якщо межi дiяльностi мiстять неконкретизованi змiннi, то встановлюється обмеження на значення змiнних, якi далi перевiряються пiсля конкретизацiї.
Loading...

 
 

Цікаве