Увидел топик про мультиагентные систему и решил кой-чего добавить на эту тему. Сосредоточусь на 2-х направлениях: чем МАС отличаются от классических систем (кроме параллельности, которая все-же и не только в МАС встречается) и на двух примерах, практическом и абстрактно-теоретическом.
Современное ПО, например, корпоративного уровня, неимоверно сложно. Усугубляет дело «масштабный фактор» — чем больше система, тем быстрее растет ее сложность, так как растет число связей между частями.
МАС является одним из способов упростить систему, так как позволяет сократить число внутренних связей в системе (если подумать, то это можно сказать почти про любую достаточно автономную систему ИИ).
Первоначально МАС появились как распределенные системы ИИ. В 1980г в MIT состоялась первый семинар на тему распределенных решателей задач ИИ, на котором поднимались вопросы эффективной координации многих агентов и демонов, разработка системы классной доски и ряд других. Некоторые считают 1980 годом рождения МАС.
Очевидно, что мультиагентные системы довольно сильно отличаются от классических систем. И, хотя первоначальной целью была именно параллельная обработка задач ИИ, сейчас основной акцент делается на раздельной обработке (в отличие от параллельной СИИ, агенты чаще решают не одинаковые задачи, в том числе конкурируют друг с другом, что видно на примере сим-лайфов) и «социальном» поведении агентов. Интересно, что МАС позволяют считать человека таким же агентом. Из этого можно извлекать профит, когда происходит постепенная замена операторов на компьютерных агентов.
Более четкие определения:
Итак, узнали общие принципы. Теперь пора делать интересные выводы о качествах МАС:
Логистика является одной традиционных и наиболее развитых сфер использования мультиагентных систем. Это вызвано большой эффективностью (при использовании МАС может происходить уменьшение расходов до нескольких сотен процентов в сравнении с ручным расчетом). Эффективность достигается за счет того, что в логистике есть достаточно большое число поставщиков товаров и достаточно большое число потребителей и, при этом, поставлять готовы больше, чем потреблять. Следовательно, наиболее опасной для МАС ситуации «драчки за ограниченные ресурсы» не происходит.
Агенты в логистике делятся на поставщиков, потребителей и курьеров. Задачей каждого курьера является оптимальная нагрузка на транспорт (чтобы «грузовик» был забит ровно на величину объема/грузоподъемности, чтобы порожних рейсов было как можно меньше, а лучше вообще не было) и оптимизация маршрута (минимизация пути и времени, хотя возможны и другие параметры, например качество дорожного покрытия, частота милицейских будок и прочее). Условием работы является полное выполнение заказов на доставку и возможность взять достаточное количество ресурсов от поставщиков.
Пример абстрактный, для того, чтобы еще раз показать принципы работы.
Обычно, планирование производства является сложно и нетривиальной задачей. Необходимо обеспечить всех исполнителей (и людей, и станки) необходимым числом деталек вовремя, чтобы они могли работать наиболее оптимальным образом. При этом, результат работы одних исполнителей влияет на работу других прямо (для работы нужны детальки, произведенные ранее) и косвенно (для сборки изделия нужно несколько видов деталей — если нет одних, то вторые тоже нельзя продолжать безудержно создавать). Вручную рассчитывать все это — адская работа, особенно если производство распределенное. В случае же использования мультиагентных систем все несколько упрощается: создаются агенты-исполнители, агенты-курьеры (доставляют продукцию от одного станка другому), задаем объемы и расписание изготовления изделий — и, собственно, все. Агенты сначала последовательно создают цепочки запросов (возможно, учитывая, уровень брака и еще какие-то особенности), обеспечивая каждого исполнителя задачами на требуемый объем и время исполнения, одновременно ожидая от исполнителей далее по цепочке исполнения своих заказов. Параметры курьеров задают размеры и количество переносимых за раз деталей между исполнителями (можно за раз перевезти три ящика мелочевки или один большой двигатель — но не наоборот) В случае, если кто-то сломался, пустил брак или еще какой астероид упал — производство в нужных местах перепланируется (с попыткой сохранить в силе обязательства агентов), и на некотором уровне даже не будет заметно, что где-то что-то сломалось. А там, где будет заметно, об этом узнают почти в момент поломки, а не когда некуда будет складывать полуфабрикаты.
На выводы это не тянет, заключением так же не является, поэтому будет «конец».
При написании статьи использовалась замечательная книга по общим вопросам систем искусственного интеллекта Люгера, небольшой личный опыт (делал маленький симлайф) и много разного сопряженного материала по проблемам распределенного СИИ. Особо отмечу некую международную компанию, которая работает над ПО по решению задач логистики с помощью МАС (оттуда взята основа для примера «логистика»).Ищу. Как только будет что-то — добавлю сюда. Нашел, склерозник… Компания называется Magenta Technology (есть «умеренно русская версия» — клик по флажку )
Литература:
Джордж Ф. Люгер Искусственный интеллект. Стратегии и методы решения сложных проблем. 4-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2003 — 846с.
Upd: благодарю уважаемую киноакадемию (не знаю за что, но так вроди полагается) мою маму за то, что она меня родила и растила и НЛО за то, что оно прилетело и дало инвайт ))
Высоколобая теория
Немного банальщины и истории
Современное ПО, например, корпоративного уровня, неимоверно сложно. Усугубляет дело «масштабный фактор» — чем больше система, тем быстрее растет ее сложность, так как растет число связей между частями.
МАС является одним из способов упростить систему, так как позволяет сократить число внутренних связей в системе (если подумать, то это можно сказать почти про любую достаточно автономную систему ИИ).
Первоначально МАС появились как распределенные системы ИИ. В 1980г в MIT состоялась первый семинар на тему распределенных решателей задач ИИ, на котором поднимались вопросы эффективной координации многих агентов и демонов, разработка системы классной доски и ряд других. Некоторые считают 1980 годом рождения МАС.
Общие принципы работы
Очевидно, что мультиагентные системы довольно сильно отличаются от классических систем. И, хотя первоначальной целью была именно параллельная обработка задач ИИ, сейчас основной акцент делается на раздельной обработке (в отличие от параллельной СИИ, агенты чаще решают не одинаковые задачи, в том числе конкурируют друг с другом, что видно на примере сим-лайфов) и «социальном» поведении агентов. Интересно, что МАС позволяют считать человека таким же агентом. Из этого можно извлекать профит, когда происходит постепенная замена операторов на компьютерных агентов.
Более четкие определения:
- ситуативность — означает, что агент воспринимает окружение и может как-либо изменять его. В окружающий мир включены все, что может «почувствовать» агент и все, с чем он может взаимодействовать (в том числе другие агенты);
- автономность — агент может взаимодействовать с окружением без вмешательства других агентов;
- гибкость — отзывчивость или предусмотрительность (в зависимости от ситуации) агента. Отзывчивость предполагает, что агент своевременно реагирует на окружающую среду и действует соответствующим образом. Предусмотрительность предполагает, что агент не только реагирует на изменения среды, но и заранее готовится к ним, адаптируется, выбирает альтернативы в различных ситуациях. Очевидно, что предусмотрительность более сложная задача, отзывчивость характерна для более простых агентов;
- социальность — агент должен не только решать свою узкую задачу в одиночку, но и взаимодействовать с окружающими его агентами, решая совместно более общую задачу системы. Для этого, обычно, в агентов встраивают механизмы (протоколы) взаимодействия, которые позволяют агентам договориться друг с другом для разрешения задач.
Особенности
Итак, узнали общие принципы. Теперь пора делать интересные выводы о качествах МАС:
- «агент» — более общее понятие, чем «система». Следовательно, любая часть сложной системы может быть представлена как агент. Не затрагивая целесообразность рассмотрения кнопки «Ок» как агента, замечу, что это позволяет универсально рассматривать систему в целом — это дает преимущество гибкости как во времени (приведенный выше пример с заменой человека-оператора на компьютерного агента), так и в структуре системы.
- в общем случае, агентам не нужен «менеджер» чтобы взаимодействовать друг с другом. Для этого есть социальные протоколы — они позволяют и договориться и организовать обмен ресурсами и данными. Впрочем, это не делает невозможным создание агента-менеджера, с которым как IRL можно договориться, забить на него и далее по списку «поведения ответственного работника».
- агенты, зачастую, не имею строгих обязанностей. Дело в том, что добиться стабильности системы при большом числе «очень исполнительных» агентов очень тяжело (кто не верит — почитайте про дедлоки при планировании ресурсов ОС). По этой причине агент может очень по разному реагировать на внешний запрос — от очень быстрого и полного исполнения, до игнорирования — в зависимости от своих внутренних соображений. Для того, чтобы сгладить этот недостаток не-гарантированности обслуживания используются социальные протоколы. В итоге недостаток превращается в огромное преимущество — вместо ломания головы над сложнейшими алгоритмами диспетчеризации огромного числа ресурсов, мы просто даем задания, а агенты сами его разбирают и сами решают как с ним поступить и как распределить ресурсы. Недостатками такого метода являются некоторая неопределенность и возможность, при большой нагрузке, накопления очередей. С очередями справляются на уровне удовлетворения потребностей системы в целом, а неопределенность является просто другой стороной того, что все решается между агентами. В итоге, все получается очень красиво.
Два примера
Логистика
Логистика является одной традиционных и наиболее развитых сфер использования мультиагентных систем. Это вызвано большой эффективностью (при использовании МАС может происходить уменьшение расходов до нескольких сотен процентов в сравнении с ручным расчетом). Эффективность достигается за счет того, что в логистике есть достаточно большое число поставщиков товаров и достаточно большое число потребителей и, при этом, поставлять готовы больше, чем потреблять. Следовательно, наиболее опасной для МАС ситуации «драчки за ограниченные ресурсы» не происходит.
Агенты в логистике делятся на поставщиков, потребителей и курьеров. Задачей каждого курьера является оптимальная нагрузка на транспорт (чтобы «грузовик» был забит ровно на величину объема/грузоподъемности, чтобы порожних рейсов было как можно меньше, а лучше вообще не было) и оптимизация маршрута (минимизация пути и времени, хотя возможны и другие параметры, например качество дорожного покрытия, частота милицейских будок и прочее). Условием работы является полное выполнение заказов на доставку и возможность взять достаточное количество ресурсов от поставщиков.
Свечной заводик
Пример абстрактный, для того, чтобы еще раз показать принципы работы.
Обычно, планирование производства является сложно и нетривиальной задачей. Необходимо обеспечить всех исполнителей (и людей, и станки) необходимым числом деталек вовремя, чтобы они могли работать наиболее оптимальным образом. При этом, результат работы одних исполнителей влияет на работу других прямо (для работы нужны детальки, произведенные ранее) и косвенно (для сборки изделия нужно несколько видов деталей — если нет одних, то вторые тоже нельзя продолжать безудержно создавать). Вручную рассчитывать все это — адская работа, особенно если производство распределенное. В случае же использования мультиагентных систем все несколько упрощается: создаются агенты-исполнители, агенты-курьеры (доставляют продукцию от одного станка другому), задаем объемы и расписание изготовления изделий — и, собственно, все. Агенты сначала последовательно создают цепочки запросов (возможно, учитывая, уровень брака и еще какие-то особенности), обеспечивая каждого исполнителя задачами на требуемый объем и время исполнения, одновременно ожидая от исполнителей далее по цепочке исполнения своих заказов. Параметры курьеров задают размеры и количество переносимых за раз деталей между исполнителями (можно за раз перевезти три ящика мелочевки или один большой двигатель — но не наоборот) В случае, если кто-то сломался, пустил брак или еще какой астероид упал — производство в нужных местах перепланируется (с попыткой сохранить в силе обязательства агентов), и на некотором уровне даже не будет заметно, что где-то что-то сломалось. А там, где будет заметно, об этом узнают почти в момент поломки, а не когда некуда будет складывать полуфабрикаты.
Конец
На выводы это не тянет, заключением так же не является, поэтому будет «конец».
При написании статьи использовалась замечательная книга по общим вопросам систем искусственного интеллекта Люгера, небольшой личный опыт (делал маленький симлайф) и много разного сопряженного материала по проблемам распределенного СИИ. Особо отмечу некую международную компанию, которая работает над ПО по решению задач логистики с помощью МАС (оттуда взята основа для примера «логистика»).
Литература:
Джордж Ф. Люгер Искусственный интеллект. Стратегии и методы решения сложных проблем. 4-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2003 — 846с.
Upd: благодарю уважаемую киноакадемию (не знаю за что, но так вроди полагается) мою маму за то, что она меня родила и растила и НЛО за то, что оно прилетело и дало инвайт ))
