Популярно об ИИ
Если не знаешь, куда идешь, придешь не туда, куда хочешь.
Йоги Берра
Итак, в прошлых материалах в качестве основы мы рассмотрели наиболее практическое представление ИИ, основанное на агентах и агентноориентированных методах "агент-действие", рассказали о реализации функции вознаграждений и т.д. Но на данный момент существует и еще несколько узкоспециализированных направлений, изучающих ИИ, которые также нельзя оставить без внимания. Среди основных задач, которые пытаются решать в их рамках — адаптация к среде, самообучение/самосовершенствование, эволюция и т.д. То есть найти наименее абстрактные ответы на эти широкие вопросы, причем так, чтобы их стало можно применять на практике.
И в данной ситуации ко всему в рамках ИИ нужно подходить, как и физики в своей науке: если им удобно, подразумевают под светом волны, а если нет — поток частиц. Классический пример такового из области искусственного интеллекта (см. рис.). Представьте себе небольшую шахматную доску, на которой две крайние по диагонали клетки (угловые) отсутствуют. И стоит задача покрыть такую доску фишками домино, каждая из которых занимает по две соседние клетки. Первый и самый очевидный вариант — это математический перебор возможных вариантов, причем зачастую программисты так бы и подошли к решению проблемы. Но если абстрагироваться от того же программирования и включить логику, то можно отметить, что, например, черных клеток на доске на две больше (или меньше), чем белых, а каждая фишка домино покрывает только одну белую и одну черную, соответственно, данную задачу решить невозможно. Вот очевидный пример использования двух различных подходов. И во втором случае это не другой вариант решения, а вообще иной взгляд на обозначенную проблему. Этим узкоспециализированные направления по изучению ИИ и ценны. Теперь мы продолжим начатую ранее тему и перейдем к конкретным примерам.
Пример №1
Допустим, у нас есть некий виртуальный город, и стоит задача его снабжения… гончарными изделиями (можете представить себе стандартную игровую экономическую стратегию типа Pharao, Caesar, CivCity:Rome, но не Capitalism II(!)). Что вы делаете в данной ситуации как стратег? Правильно. Вычисляете потребности и строите определенное количество мастерских. При этом на самом деле вы не (!) рассматриваете варианты разнообразия и качества поставляемой продукции. То есть все утрировано до планирования "в каждый дом по горшку". А если точнее, в каждый стандартный дом, в котором живет стандартный житель, по стандартному горшку. Ничего не напоминает? Правильно, коммунистическую модель (назовем ее так). И, кстати, она очень удобна с точки зрения планирования в рамках закрытой системы с минимумом неопределенностей. Чтобы не было шатких моментов с терминологией, назовем эту модель вариантом 1. А теперь посмотрим на все не с точки зрения некоего глобального разума, а конкретного агента — мастерской. В его рамках планирование предсказуемо, причем оно практически не предусматривает никакого прогресса — основными элементами являются спрос и его удовлетворение, то есть, как говорили раньше, выполнение плана.
Среда агента является статической, потому постановка (формулировка) и решение задач делаются без учета изменений, которые могут в ней произойти. Все максимально детерминируемо, то есть предсказуемо. При этом агенту не обязательно отслеживать акты восприятия со стороны среды — он чувствует себя уверенно, решая поставленные задачи. В теории управления такие системы называют системами с разомкнутой обратной связью. Если мы не будем зацикливаться на экономической модели, то практически схожую аналогию вы можете провести с системами поиска и составления оптимальных маршрутов следования, когда имеется карта. Здесь тоже все детерминируемо, среда статична, а система не имеет обратной связи. Можно привести еще большое количество подобных примеров.
…№2
Но в жизни все происходит не так ровно, и, возвращаясь к нашему примеру с мастерскими, можно отметить, что один агент (мастерская) из многих может выпускать более красивую и/или качественную и/или дешевую продукцию, соответственно, к нему будет перетекать больший покупательский поток и т.д. В таком случае эта мастерская начинает развиваться, укрупняться и совершенствоваться, в то время как некоторые другие производства сходят на нет либо же предпринимают попытки к улучшению, исходя из сложившейся ситуации. И не факт, что первая в итоге останется в выигрышном положении… это даже больше не капиталистическая модель, а дарвинистская модель естественного отбора. Так построена природа, так работает эволюция, так появился человеческий разум. С точки зрения мастерской нужно учитывать ряд факторов, сопутствующих состоянию рынка, поведению конкурентов и т.д. Среда агента является динамической и недетерминированной, проведение обратной связи со средой просто необходимо. А самому агенту нужны более сложные алгоритмы планирования.
Но на самом деле, очень часто в рамках ИИ мы можем увидеть тяготение от этого варианта к первому. То есть максимального устранения неопределенностей и динамизма, получения предсказуемости. Кстати, об этом мы очень много говорили в позапрошлом материале этой серии. На данный момент стоит остановиться на решении задач детерминированного типа в рамках статической среды.
Задача поиска маршрута и другие
Представим, что мы должны, имея карту города, составить маршрут следования из одного его конца в другой. Рассмотрим это как задачу, в которой имеются:
. Начальное состояние. То есть точка отправления.
. Другие состояния, т.е. промежуточные пункты следования, которые могут описываться расстоянием либо временем следования.
. Цель. Точка прибытия.
В рамках задачи мы выполним вычисления, в пределах которых используется так называемая функция определения преемника, то есть расчета следующего оптимального состояния из имеющихся. При этом происходит сверка с конечной целью, а также с оценочной функцией (например, стоимость поездки), которая может быть сопутствующим влияющим фактором для данного алгоритма. При этом, рассчитывая путешествия, нужно учитывать ряд сопутствующих факторов — например, предусмотреть варианты действий в непредвиденных ситуациях, то есть альтернативные маршруты, использование других видов транспорта и т.п.
Это самый простой вариант. Но допустим, помимо этого, у вас стоит задача обязательно посетить несколько промежуточных пунктов, и распланировать это нужно наиболее оптимальным способом. Эта задача известна как "задача коммивояжера" (Traveling Salesperson Problem — TSP). По ее условию каждый город на карте определенной области должен быть посещен только один раз. И это очень важно, поскольку лишняя дорога — это затраты, вычитаемые из прибыли. Сама задача коммивояжера имеет множество сфер применения — например, в промышленности нужно рассчитать перемещения сверла при создании отверстий в печатных платах и т.д. Примерно схожие проблемы решатся в рамках автоматизации сборки, упорядочивания процессов, точного определения их следования друг за другом. Такие же вопросы решаются и в механизмах поиска (интернет и т.п.).
Поиск
А в общем и целом все заключается в поиске в пространстве состояний. В рамках задачи соответственно создается дерево поиска. Слово "дерево" говорит само за себя. Соответственно, начальное состояние называется узлом поиска, после которого происходит развертывание текущего состояния до множества последующих состояний. И тут важно отметить один ключевой момент. В игре крестики-нолики на расчерченной доске имеется всего 9 состояний. Но если создавать дерево поиска ходов, то в его рамках это количество состояний значительно увеличивается. То есть нельзя путать пространство состояний с деревом поиска. Поскольку мы уже вплотную подошли к практике, изложение основ которой должно занимать достаточно много места, на сегодня ограничимся тем, что есть.
В принципе, нужно понять одно — что даже если существует некая неопределенность, человек, а он так себя ведет и в природе, аппроксимирует задачу до границ определенности. При необходимости абстрагирует, то есть отделяет необходимые вводные данные для постановки самой задачи и принятия решений, отчленяет ненужные ветви. Ведь для составления маршрута из Минска в Борисов можно взять в учет и карту мира. И тут все зависит от задачи. Например, если между Минском и Борисовом вам нужно залететь в Нью-Йорк. Экономические же модели создаются по схожим принципам, о чем мы также подробно расскажем. Хотя, даже сейчас вы можете на базе примера №2 попробовать создать дерево развития предприятия при условиях, что у вас есть начальный капитал, и нужно достичь цели — выпустить 1000 единиц товара.
Продолжение следует.
Кристофер, christopher@tut.by
Йоги Берра
Итак, в прошлых материалах в качестве основы мы рассмотрели наиболее практическое представление ИИ, основанное на агентах и агентноориентированных методах "агент-действие", рассказали о реализации функции вознаграждений и т.д. Но на данный момент существует и еще несколько узкоспециализированных направлений, изучающих ИИ, которые также нельзя оставить без внимания. Среди основных задач, которые пытаются решать в их рамках — адаптация к среде, самообучение/самосовершенствование, эволюция и т.д. То есть найти наименее абстрактные ответы на эти широкие вопросы, причем так, чтобы их стало можно применять на практике.
И в данной ситуации ко всему в рамках ИИ нужно подходить, как и физики в своей науке: если им удобно, подразумевают под светом волны, а если нет — поток частиц. Классический пример такового из области искусственного интеллекта (см. рис.). Представьте себе небольшую шахматную доску, на которой две крайние по диагонали клетки (угловые) отсутствуют. И стоит задача покрыть такую доску фишками домино, каждая из которых занимает по две соседние клетки. Первый и самый очевидный вариант — это математический перебор возможных вариантов, причем зачастую программисты так бы и подошли к решению проблемы. Но если абстрагироваться от того же программирования и включить логику, то можно отметить, что, например, черных клеток на доске на две больше (или меньше), чем белых, а каждая фишка домино покрывает только одну белую и одну черную, соответственно, данную задачу решить невозможно. Вот очевидный пример использования двух различных подходов. И во втором случае это не другой вариант решения, а вообще иной взгляд на обозначенную проблему. Этим узкоспециализированные направления по изучению ИИ и ценны. Теперь мы продолжим начатую ранее тему и перейдем к конкретным примерам.
Пример №1
Допустим, у нас есть некий виртуальный город, и стоит задача его снабжения… гончарными изделиями (можете представить себе стандартную игровую экономическую стратегию типа Pharao, Caesar, CivCity:Rome, но не Capitalism II(!)). Что вы делаете в данной ситуации как стратег? Правильно. Вычисляете потребности и строите определенное количество мастерских. При этом на самом деле вы не (!) рассматриваете варианты разнообразия и качества поставляемой продукции. То есть все утрировано до планирования "в каждый дом по горшку". А если точнее, в каждый стандартный дом, в котором живет стандартный житель, по стандартному горшку. Ничего не напоминает? Правильно, коммунистическую модель (назовем ее так). И, кстати, она очень удобна с точки зрения планирования в рамках закрытой системы с минимумом неопределенностей. Чтобы не было шатких моментов с терминологией, назовем эту модель вариантом 1. А теперь посмотрим на все не с точки зрения некоего глобального разума, а конкретного агента — мастерской. В его рамках планирование предсказуемо, причем оно практически не предусматривает никакого прогресса — основными элементами являются спрос и его удовлетворение, то есть, как говорили раньше, выполнение плана.
Среда агента является статической, потому постановка (формулировка) и решение задач делаются без учета изменений, которые могут в ней произойти. Все максимально детерминируемо, то есть предсказуемо. При этом агенту не обязательно отслеживать акты восприятия со стороны среды — он чувствует себя уверенно, решая поставленные задачи. В теории управления такие системы называют системами с разомкнутой обратной связью. Если мы не будем зацикливаться на экономической модели, то практически схожую аналогию вы можете провести с системами поиска и составления оптимальных маршрутов следования, когда имеется карта. Здесь тоже все детерминируемо, среда статична, а система не имеет обратной связи. Можно привести еще большое количество подобных примеров.
…№2
Но на самом деле, очень часто в рамках ИИ мы можем увидеть тяготение от этого варианта к первому. То есть максимального устранения неопределенностей и динамизма, получения предсказуемости. Кстати, об этом мы очень много говорили в позапрошлом материале этой серии. На данный момент стоит остановиться на решении задач детерминированного типа в рамках статической среды.
Задача поиска маршрута и другие
Представим, что мы должны, имея карту города, составить маршрут следования из одного его конца в другой. Рассмотрим это как задачу, в которой имеются:
. Начальное состояние. То есть точка отправления.
. Другие состояния, т.е. промежуточные пункты следования, которые могут описываться расстоянием либо временем следования.
. Цель. Точка прибытия.
В рамках задачи мы выполним вычисления, в пределах которых используется так называемая функция определения преемника, то есть расчета следующего оптимального состояния из имеющихся. При этом происходит сверка с конечной целью, а также с оценочной функцией (например, стоимость поездки), которая может быть сопутствующим влияющим фактором для данного алгоритма. При этом, рассчитывая путешествия, нужно учитывать ряд сопутствующих факторов — например, предусмотреть варианты действий в непредвиденных ситуациях, то есть альтернативные маршруты, использование других видов транспорта и т.п.
Это самый простой вариант. Но допустим, помимо этого, у вас стоит задача обязательно посетить несколько промежуточных пунктов, и распланировать это нужно наиболее оптимальным способом. Эта задача известна как "задача коммивояжера" (Traveling Salesperson Problem — TSP). По ее условию каждый город на карте определенной области должен быть посещен только один раз. И это очень важно, поскольку лишняя дорога — это затраты, вычитаемые из прибыли. Сама задача коммивояжера имеет множество сфер применения — например, в промышленности нужно рассчитать перемещения сверла при создании отверстий в печатных платах и т.д. Примерно схожие проблемы решатся в рамках автоматизации сборки, упорядочивания процессов, точного определения их следования друг за другом. Такие же вопросы решаются и в механизмах поиска (интернет и т.п.).
Поиск
А в общем и целом все заключается в поиске в пространстве состояний. В рамках задачи соответственно создается дерево поиска. Слово "дерево" говорит само за себя. Соответственно, начальное состояние называется узлом поиска, после которого происходит развертывание текущего состояния до множества последующих состояний. И тут важно отметить один ключевой момент. В игре крестики-нолики на расчерченной доске имеется всего 9 состояний. Но если создавать дерево поиска ходов, то в его рамках это количество состояний значительно увеличивается. То есть нельзя путать пространство состояний с деревом поиска. Поскольку мы уже вплотную подошли к практике, изложение основ которой должно занимать достаточно много места, на сегодня ограничимся тем, что есть.
В принципе, нужно понять одно — что даже если существует некая неопределенность, человек, а он так себя ведет и в природе, аппроксимирует задачу до границ определенности. При необходимости абстрагирует, то есть отделяет необходимые вводные данные для постановки самой задачи и принятия решений, отчленяет ненужные ветви. Ведь для составления маршрута из Минска в Борисов можно взять в учет и карту мира. И тут все зависит от задачи. Например, если между Минском и Борисовом вам нужно залететь в Нью-Йорк. Экономические же модели создаются по схожим принципам, о чем мы также подробно расскажем. Хотя, даже сейчас вы можете на базе примера №2 попробовать создать дерево развития предприятия при условиях, что у вас есть начальный капитал, и нужно достичь цели — выпустить 1000 единиц товара.
Продолжение следует.
Кристофер, christopher@tut.by
Компьютерная газета. Статья была опубликована в номере 23 за 2008 год в рубрике технологии
