Универсальный решатель задач

Google docs — https://docs.google.com/document/pub?id=1XYn_UUKKrKQW0DOUGlmt6Rnk5p4Uz5JGDWIZZT_BnsU

Рыбинск, 2011

Оглавление

Оглавление        

Введение        

Основы функционирования универсального решателя задач        

Диаграмма достижения цели        

Пример реализации УРЗ на языке Ruby        

Вывод        

Список литературы        


Введение

Универсальный решатель задач (General problem solver, GPS) – компьютерная программа, которую разработали А. Ньюелл и Г. Саймон Newell, Simon, 1959 . это была первая программа, которая моделировала процесс решения задач человеком. УРЗ основан на анализе целей и средств, т. е. в программе воспроизводились способы, которыми люди пытаются решать проблемы. Предполагалось, что тестирование программы посредством сравнения с этапами процесса решения проблем людьми позволит разработать теорию мышления. УРЗ применялся для решения таких задач, как проблема Хоббитов и Орков, грамматический анализ предложений, доказательства в логических и тригонометрических задачах.


Основы функционирования универсального решателя задач

Название «Универсальный решатель задач» обусловлено тем фактом, что это была первая система для решения задач (problem-solving system), в которой общие методы решения были отделены от знаний, определяющих конкретную задачу. Часть программы, осуществлявшая поиск решения, не обладала информацией о конкретном виде задачи, с которой она работала. Специфичные для конкретной задачи знания организовывались в отдельные структуры: объекты и операторы для преобразования объектов. Задача для системы GPS ставилась в виде пары, состоящей из начального объекта и желаемого объекта, в который начальный объект должен быть преобразован.

Методология, использованная в GPS, отличается от стандартных методов поиска в пространстве состояний тем, что она выбирает путь, по которому продолжить поиск. Т.е. система пытается искать решение в первую очередь в «наиболее перспективных» ветвях поиска. Такая методология была названа «анализ средств и целей» (means-ends analysis). Ее суть заключалась в том, что сначала отыскивалось различие (difference) между текущим объектом и объектом, который мы хотим получить. Это различие относилось к одному из ряда классов различий. С каждым классом был сопоставлен набор действий, способных уменьшить различие между текущим и целевым объектами.

Хотя GPS может решить простые задачи, такие как Башни Ханоя, которые могли бы быть формализованы, она не может решить многие проблемы реального мира, потому что поиск решения затруднится комбинаторным взрывом для промежуточных состояний.

На каждом шаге поиска GPS искал различие объектов и выбирал один из релевантных операторов, который и пытался затем применить к текущему объекту. Поиск подходящей последовательности операторов выполнялся в глубину до тех пор, пока операторы оказывались применимы, а ветвь поиска «выглядела перспективной». Если ветвь поиска была бесперспективной, то выполнялся откат. Важной особенностью анализа средств и целей является то, что всегда выбирается «релевантный» оператор, уменьшающий различие объектов, даже если он и не применим к текущему объекту. Вместо того чтобы отказаться от неприменимого к текущему объекту оператора, GPS пытался преобразовать текущий объект в объект, пригодный для применения выбранного оператора. Применение такой стратегии привело к появлению рекурсивной, целеориентированной процедуры, которая фиксирует историю поиска в графе с частично-проработанными узлами.

Несмотря на то, что в качестве объекта могла выступать модель мира, а в качестве оператора — действие, задача планирования перед системой GPS не ставилась. Такой вариант использования GPS был осуществлен значительно позднее, когда была разработана система STRIPS.

Среди основных характеристик УРЗ следует выделить:

  1. Рекурсивный характер ее способности решать задачи
  2. Отделение содержимого задачи от метода решения задачи, как путь увеличения универсальности программы.
  3. Два основных метода решения задач, как то: анализ средств-целей и планирование.
  4. Организация программы и запоминающее устройство, используемое для механизации программы.


Диаграмма достижения цели

оценка цели

Выбор метода для данной цели

Применение метода

Цель достигнута

Цель  не достигнута

принято

отвергнуто

Не пытаемся достигнуть


Пример реализации УРЗ на языке Ruby

Рассмотрим первую версию УВЗ, основанную на классической лисп-реализации УВЗ.

class GPS
 
Op = Struct.new(:action, :preconds, :add_list, :del_list)

 def initialize(state, ops)
   
@state = state
   
@ops = ops
 
end

 # General Problem Solver  — основной интерфейс: достигаем всех целей используя
 # указанные операции
 def solve(*goals)
   goals.all?
do |goal|
     achieve goal
   
end
 
end

 # Цель достигнута, если она уже имеется
 # или существует соответствующий op, являющееся применимым.
 def achieve(goal)
   
@state.include?(goal) ||
     (
@ops.find_all do |op|
        appropriate?(goal, op)
      
end.any? do |op|
        apply(op)
      
end)
 
end

 #op применима к цели, если она находится в списке добавления.
 def appropriate?(goal, op)
   op.add_list.include?(goal)
 
end

 #Выводим сообщение и обновляем состояние если op применимо
 def apply(op)
   
if op.preconds.all? { |cond| achieve(cond) }
     puts
«Executing #{op.action}«
     
@state -= op.del_list
     
@state += op.add_list
     
return true
   
end
   
false
 
end
end

Метод инициализации класса получает состояние и доступные Op. State и ops являются массивом состояний и массовом объектов op соответственно. Каждый из op состоит из действия, предварительных условий, списка удаления и добавления.
Основная часть кода представляет из себя метод-решатель. Он функционально соответствует оригинальному коду. Основным отличием является то, что объекты передаются во время инициализации.

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

Метод appropriate? мог бы быть добавлен к классу Op вместо Gps класса , в связи с тем, что он проверяет что add-list  операции содержит цель, что означает применимость операции к цели.
Также мы имеем apply метод  (называемый apply-op в коде Norvig’а). В данном методе применяются рекурсивные элементы алгоритма. Для применимости операции все предварительные условия должны быть заполнены.

Мы используем метод all? для попытки достижения всех предварительных условий, и в случае успеха выводится информация о примененном действии, изменяем состояние удаляя значение из  delete-list и добавляя в add-list, и в конце возвращаем истину.
        Перейдем к тестированию и применению данного варианта УРЗ. Для проверки используем схожую с классической информацию о «путешествии в начальную школу».

Опишем набор операций:
SCHOOL_OPS = [
               
Op.new(:drive_son_to_school,
                      [
:son_at_home, :car_works],
                      [
:son_at_school],
                      [
:son_at_home]),
               
Op.new(:shop_installs_battery,
                      [
:car_needs_battery, :shop_knows_problem,
                       
:shop_has_money],
                      [
:car_works],
                      []),
               
Op.new(:tell_shop_problem,
                      [
:in_communication_with_shop],
                      [
:shop_knows_problem],
                      []),
               
Op.new(:telephone_shop,
                      [
:know_phone_number],
                      [
:in_communication_with_shop],
                      []),
               
Op.new(:look_up_number,
                      [
:have_phone_book],
                      [
:know_phone_number],
                      []),
               
Op.new(:give_shop_money,
                      [
:have_money],
                      [
:shop_has_money],
                      [
:have_money])
              ]
Теперь рассмотрим проблемы.

Первая проблема  problem1.rb:
require
‘gps’

gps = GPS.new([:son_at_home,
              
:car_needs_battery,
              
:have_money,
              
:have_phone_book],
             
GPS::SCHOOL_OPS)
if gps.solve(:son_at_school)
 puts
«Solved»
else
 puts
«Not solved»
end

Текущее состояние говорит, что сын находится в школе, аккумулятор автомобиля должен быть заряжен, и есть деньги и записная книжка. Целью является доставка сына в школу. Если мы запустим данный код, то получим следующее:

Executing look_up_number
Executing telephone_shop
Executing tell_shop_problem
Executing give_shop_money
Executing shop_installs_battery
Executing drive_son_to_school
Solved
Решение обнаружено.

Теперь рассмотрим проблему, когда записная книжка отсутствует (problem2.rb):
require
‘gps’

gps = GPS.new([:son_at_home,
              
:car_needs_battery,
              
:have_money],
             
GPS::SCHOOL_OPS)

if gps.solve(:son_at_school)
 puts
«Solved»
else
 puts
«Not solved»
end
В результате мы получим результат:
Not solved
что является ожидаемым результатом.

Теперь рассмотрим пример, когда машина функционирует  (problem3.rb):
require
‘gps’

gps = GPS.new([:son_at_home,
              
:car_works],
             
GPS::SCHOOL_OPS)

if gps.solve(:son_at_school)
 puts
«Solved»
else
 puts
«Not solved»
end
В результате мы получим:
Executing drive_son_to_school
Solved

Но в данной версии УРЗ имеются некоторые проблемы. Во-первых, УРЗ не решает некоторые достаточно простые проблемы.

Решения могут быть некорректны для длительных действий. Норвиг называет это » The Running around the block problem «. Это легко определить цель езды от дома до школы, но это немного сложнее представлять бегают блока. Есть способы обойти это, конечно, но оператор GPS не обязательно делать это же естественно, как это могло быть.

Другой, более серьезной проблемой является «clobber sibling goal problem». В случае как problem4.rb все обрабатывается корректно:


require
‘gps’

gps = GPS.new([:son_at_home,
              
:have_money,
              
:car_works],
             
GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
 puts
«Solved»
else
 puts
«Not solved»
end
Но если мы создадим слебдующую проблему
problem5.rb:
require
‘gps’

gps = GPS.new([:son_at_home,
              
:car_needs_battery,
              
:have_phone_book,
              
:have_money],
             
GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
 puts
«Solved»
else
 puts
«Not solved»
end

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

Путем решения данной проблемы будет являться замена вызова метода achieve на вызов нового метода achieve_all. Рассмотрим модифицированную версию УРЗ gps_no_clobber.rb:
require
‘gps’

class Array
 
def subset_of?(other)
   (
self — other) == []
 
end
end

class GPS
 
def solve(*goals)
   achieve_all goals
 
end

 def apply(op)
   
if achieve_all(op.preconds)
     puts
«Executing #{op.action}«
     
@state -= op.del_list
     
@state += op.add_list
     
return true
   
end
   
false
 
end

 def achieve_all(goals)
   goals.all?
do |goal|
     achieve goal
   
end && goals.subset_of?(@state)
 
end
end
В результате метод achieve_all позволяет достигнуть всех целей, с проверкой достижимости всех целей в текущем состоянии.
В случае запуска
 problem6.rb:
require
‘gps_no_clobber’

gps = GPS.new([:son_at_home,
              
:car_needs_battery,
              
:have_phone_book,
              
:have_money],
             
GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
 puts
«Solved»
else
 puts
«Not solved»
end

Мы получим на выводе несколько примененных действий, и в результате сообщение «Not solved», так как обе цели одновременно не достижимы. 


Вывод

В данном документы мы рассмотрели основное описание универсального решателя задач и пример реализации УРЗ (на основе классической Лисп реализации), рассмотрев некоторые проблемы полученного варианта решения.


Список литературы

  1. Newell A., Shaw J. C., Simon H. A., Report on a general problem-solving program. IFIP Congress, 1959
  2. Ola Bini, Chicago, http://olabini.com, 2010
  3. Трофимов И.В. http://ai-center.botik.ru/planning/index.php?ptl=materials/gps-overview.htm, апрель 2005 год.

Моделирование систем
Вопросы для самопроверки и контроля

  1. Основные задачи моделирования систем
  2. Классификация методов моделирования систем
  3. Основные понятия моделирования систем
  4. Модель двоичного выбора
  5. Модель системы хищник-жертва
  6. Модель динамики водохранилища
  7. Модель макроэкономики (Леонтьева)
  8. Внутреннее и внешнее описание систем
  9. Потенциальная функция системы
  10. Локальные и глобальные модели
  11. Общие принципы системной организации: устойчивость, управляемость и наблюдаемость
  12. Инвариантность и чувствительность систем управления
  13. Классификация моделей систем
  14. Коммутативные диаграммы. Матрицы достижимости и наблюдаемости реализации. Минимальные модели.
  15. Модели теории катастроф.
  16. Пространство состояний и процессы в пространстве состояний. Статистическая система и динамическая система. Линейные и нелинейные системы.
  17. Отображение вход-выход для линейной системы.
  18. Фундаментальная теория линейной теории системы.
  19. Пространство состояний как модуль.
  20. Фундаментальная теорема линейной теории реализации
  21. Алгоритм матричных инвариантов
  22. Классификация типов сложности систем
  23. Классификация типов устойчивости систем
  24. Структурная устойчивость
  25. Структурно устойчивая динамика. Теория катастроф.
  26. Классификация методов идентификации систем.
  27. Методические модели моделирующих программных систем.
  28. Принципы имитационного моделирования систем.
  29. Теоретико-множественные модели систем. Многоосновные алгебры структур данных. Базовые алгебры структур данных.
  30. Мат. задачи системного анализа.