Мивары: 25 лет создания искусственного интеллекта - [64]

Принцип эффективного глобального поиска решений довольно естественен для прикладных задач в ограничениях, большая часть из которых является NP-полными. В отличие от методов распространения, направленных на пропозициональный вывод и локальное улучшение частных решений, методы глобального поиска обеспечивают систематический или стохастический поиск общих решений, удовлетворяющих всем заданным ограничениям. Заметим, что поиск с возвратом (backtracking) в сочетании с локальным распространением нашел применение практически во всех реализациях систем программирования в ограничениях, включая упомянутые выше диалекты языков Lisp и Prolog.

Программирование в ограничениях – это программирование в терминах "постановок задач". Постановка задачи – это конечный набор переменных V = {v[1], … v[n]}, соответствующих им конечных (перечислимых) множеств значений D = {D[1], …D[n]}, и набор ограничений С = {C[1]…C[m]}. Ограничения представлены как утверждения, в которые входят в качестве параметров переменные из некоторого подмножества V[j],j=1..m набора V. Решение такой задачи – набор значений переменных, удовлетворяющий всем ограничениям C[j].

Синтаксически такую постановку задачи можно записать как правило для "типизированного" Пролога. Семантически программирование в ограничениях отличается от традиционного логического программирования в первую очередь тем, что исполнение программы рассматривается не как доказательство утверждения, а нахождение значений переменных. При этом порядок удовлетворения отдельных ограничений не имеет значения, и система программирования в ограничениях, как правило, стремится оптимизировать порядок доказательства утверждений с целью минимизации отката в случае неуспеха. С этой целью набор ограничений может быть соответствующим образом преобразован по правилам, аналогичным правилам Пролога. Любую задачу можно рассматривать как ограничение: значения переменных должны быть решением этой задачи. Часто о программировании в ограничениях говорят исключительно как о дополнительной ветви логического программирования.

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

Как и логическое программирование, программирование в ограничениях предполагает совершенно аналогичную "естественную" реализацию на параллельных платформах.

7.2.1.2. Мультиагентные системы

Многоагентные системы – новая, современная, одна из наиболее перспективных на данный момент технологий в области искусственного интеллекта.

Под агентом понимается некоторая сущность, существующая в некоторой внешней по отношению к ней среде, функционирующая по определенны для нее законам с учетом внешней среды и в соответствии с поставленной перед ней целью. Такой агент может быть, например, роботом, программой или отдельной ее функцией, а также человеком. При этом агента можно назвать интеллектуальным, если он взаимодействует с окружающей средой примерно так же, как действовал бы человек.

Многоагентные системы состоят из нескольких, может быть, из многих взаимодействующих между собой агентов, "… каждый их которых является нераспределенной системой, основанной на знаниях, правилах и логических рассуждениях" [21]. Каждый агент должен включать в себя элементы, которые будут обеспечивать безопасность его работы, мобильность, возможность взаимодействия с другими агентами, с пользователем, использование общих сетевых ресурсов (например, сетевые БД).

Если агенты являются разнородными (по структуре, решаемым задачам, свойствам и т.д.), то говорят о гетерогенной МАС.

Многоагентные системы используют для:

· систем решения крупных логико – вычислительных задач, разбиваемых на более мелкие подзадачи, которые могут решаться параллельно;

· моделирования поведения сложных систем (состоящих из большого числа компонентов, отличающихся сложным поведением);

· систем принятия консолидированных решений.

7.2.1.2.1. Применение МАС для систем решения

На данный период времени функционирование решающих систем на основе МАС происходит следующим образом (рисунок 80):

1. система получает запрос на решение какой-либо задачи. Агент-субординатор разбивает эту общую задачу на подзадачи и распределяет их между агентами-исполнителями;

2. агенты – исполнители находят решения порученных им подзадач;

3. агент-интегратор объединяет предлагаемые агентами-исполнителями результаты в решение исходной задачи.

Рисунок 80 – Решение задачи многоагентной системой

Также МАС могут использоваться для решения одной небольшой задачи разными способами (для каждого агента определен один способ) с последующим выбором наилучшего. За счет того что поиск оптимального решения осуществляется МАС без внешнего вмешательства, МАС относятся к числу самоорганизующихся систем [21, стр. 49].

В соответствии с [21, стр.48 – 49], к числу главных теоретических проблем МАС относятся:

· описание, декомпозиция и распределение задач между агентами в многоагентной системе, синтез (композиция) решений;