Розв’язання задач методом редукції

Метод редукції приводить до гарних результатів тому, що часто розв’язання задач має ієрархічну структуру. Однак необов'язково основну задачу і всі її підзадачі розв’язувати однаковими методами. Редукція ефективна для подання глобальних аспектів задачі, а в процесі розв’язання більш специфічних задач краще застосовувати метод планування за станами. Метод планування за станами можна розглядати як окремий випадок методу планування за допомогою редукцій, тому що кожне застосування оператора в просторі станів означає зведення вхідної задачі до двох більш простих, одна з яких є елементарна. У загальному випадку редукція вхідної задачі не зводиться до формування таких двох підзадач, із яких хоча б одна була елементарною.

Пошук планування в просторі задач полягає в послідовному зведенні вхідної задачі до все більш простої, доки не будуть отримані тільки елементарні задачі. Частково впорядкована сукупність таких задач складе розв’язок вихідної задачі. Розчленування задачі на альтернативні множини підзадач зручно подавати у вигляді І/АБО-графа. У такому графі будь-яка вершина, крім кінцевої, має або кон’юнктивно зв'язані дочірні вершини (І-вершина), або диз’юнктивно зв'язані (АБО-вершина). За відсутності І-вершин має місце граф простору станів. Кінцеві вершини є або заключні (їм відповідають елементарні задачі), або тупикові. Початкова вершина (корінь І/АБО-графа) відображає вхідну задачу. Мета пошуку на І/АБО-графі – показати, що початкова вершина розв'язувана. Розв'язувані є заключні вершини (І-вершини), у яких розв'язувані всі дочірні вершини, і АБО-вершини, у яких розв'язувана хоча б одна дочірня вершина. Розв'язувальний граф складається з розв'язуваних вершин і вказує спосіб розв'язання початкової вершини. Наявність тупикових вершин приводить до нерозв'язуваних вершин. Нерозв'язувані є тупикові вершини, І-вершини, у яких нерозв'язувана хоча б одна дочірня вершина, і АБО-вершини, у яких нерозв'язувана кожна дочірня вершина.

Алгоритм Ченга і Слейгла ґрунтується на перетворенні довільного І/АБО-графа на спеціальний АБО-граф, кожна АБО-гілка якого має І-вершини тільки в кінці. Перетворення використовує подання довільного І/АБО-графа як довільної формули логіки висловлювань із подальшим перетворенням цієї довільної формули на диз'юнктивну нормальну форму. Таке перетворення дозволяє далі застосовувати алгоритм Харта, Нільсона і Рафаеля.

Метод ключових операторів. Нехай задано задачу <A, B> і відомо, що оператор f обов'язково повинен входити до розв’язку цієї задачі. Такий оператор називають ключовим. Нехай для застосування f необхідний стан C, а результат його застосування є I(c). Тоді І-вершина <A,В> породжує три дочірні вершини: <A, C>, <C, f(c)> і <f(c), B>, середня з яких становить елементарну задачу. До задач <A, C> і <f(c), B> також добирають ключові оператори, і зазначену процедуру редукування повторюють, доки це можливо. У підсумку вхідна задача <A, B> розбивається на впорядковану сукупність підзадач, кожну з яких розв’язують методом планування в просторі станів.

Можливі альтернативи щодо вибору ключових операторів, так що в загальному випадку буде мати місце І/АБО-граф. У більшості задач вдається не виділити ключовий оператор, а тільки вказати множину, яка його містить. У цьому разі для задачі <A, B> обчислюють розходження між A і B, відповідно до якого ставлять оператор, що усуває це розходження. Останній і є ключовий.

Метод планування загального розв’язувача задач (ЗРЗ). ЗРЗ став першою найбільш відомою моделлю планувальника. Його застосовували для розв’язання задач інтегрального числення, формування логічного висновку, граматичного розбору й ін. ЗРЗ поєднує два основні принципи пошуку: аналіз цілей і засобів та рекурсивне розв’язання задач. У кожному циклі пошуку ЗРЗ розв’язує в чіткій послідовності три типи стандартних задач: перетворити об'єкт А на об'єкт В, зменшити розходження D між А й В, застосувати оператор f до об'єкта А. Розв’язок першої задачі визначає розходження D, другої – придатний оператор f, третьої – необхідну умову застосування С. Якщо С не відрізняється від A, то оператор f застосовується, у противному разі С подається як чергова мета і цикл повторюється, починаючи із задачі „перетворити A на С”. У цілому стратегія ЗРЗ здійснює зворотний пошук від заданої мети В до необхідного способу її досягнення С, застосовуючи редукцію вихідної задачі <A, В> до задач <A, C> і <С, В>. Зазначимо, що в ЗРЗ за замовчуванням передбачено незалежність розходжень одне від одного, звідки випливає гарантія, що зменшення одних розходжень не призведе до збільшення інших.

Планування за допомогою логічного виведення передбачає: опис станів у вигляді правильно побудованих формул (ППФ) деякого логічного числення, опис операторів у вигляді або ППФ, або правил переведення одних ППФ в інші. Подання операторів у вигляді ППФ дозволяє створювати дедуктивні методи планування, а подання у вигляді правил переведення – методи планування з елементами дедуктивного виведення.

Дедуктивний метод планування системи QA3. ЗРЗ не виправдав сподівань, які покладали на нього, в основному через незадовільне подання задач. Спроба виправити становище привела до створення запитально-відповідної системи QA3. Система розрахована на довільну предметну галузь і здатна шляхом логічного виведення відповісти на запитання, чи можна досягти стану В з A. Як метод автоматичного виведення в системі застосовано принцип резолюцій. Для напрямку логічного виведення QA3 застосовує різні стратегії, в основному синтаксичного характеру, що враховують особливості формалізму принципу резолюцій. Експлуатація QA3 показала, що виведення в такій системі повільне, детальне, що невластиво міркуванням людини.

У методі продукцій системи STRIPS оператор подає продукцію Р, А≥В, де Р, А і В – множини ППФ числення предикатів першого порядку; Р виражає умови застосування ядра продукції А≥В; де В містить список доданих ППФ, тобто постумови. Метод повторює метод ЗРЗ з тією відмінністю, що стандартні задачі визначення розходжень і застосування придатних операторів розв’язуються на основі принципу резолюцій. Придатний оператор вибирається так само, як у ЗРЗ, на основі принципу „аналіз засобів і цілей”. Наявність комбінованого методу планування дозволила обмежити процес логічного виведення описом стану зовнішнього світу, а процес породження нових таких описів залишити за евристикою „від мети до способу її досягнення”.

Метод продукцій, що використовують макрооператори. Макрооператори – узагальнені розв’язки задач, одержувані методом STRIPS. Застосування макрооператорів дозволяє скоротити пошук розв’язку, однак при цьому постає проблема спрощення застосовуваного макрооператора, суть якої полягає у виділенні за заданим розходженням його необхідної частини й виключенні з останньої непотрібних операторів.