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

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

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

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

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

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

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

Зазначимо, що в ЗВЗ за замовчанням передбачається незалежність розходжень одне від іншого, звідки потрібна гарантія, що зменшення одних розходжень не приведе до збільшення інших.

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

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

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