ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
98
Шаг 6.
Лидер выбирает лучшую (наименее затратную) из своих
задач (например, задачу
k
)
и отправляет запрос остальным агентам:
«
У кого
k
-
я задача также является лучшей?»
Шаг 7.
Аукционер формирует структуру данных, содержащую
номера ответивших агентов и их соответствующие «цены». Кроме
того, лидер (аукционер) вносит в структуру собственные данные.
Шаг 8.
В зависимости от числа элементов массива возможны три
ситуации, описанные в табл. 3.
Таблица 3
Ситуации, возникающие в ходе проведения аукциона
Условие
Действие
Выбор всех
роботов
массива
Выбор роботов,
предложивших
наименьшую
цену
Оповещение робо-
тов о выполнении
задачи
k
Исключение
задачи
k
из
ценовых мас-
сивов роботов
Количе-
ство эле-
ментов
массива
=
n
k
+
–
+
+
<
+
–
+
–
>
–
+
+
+
Шаг 9.
Переход к шагу 4. Алгоритм выполняется до тех пор, пока
ценовые массивы роботов содержат хотя бы один элемент.
Пример.
Рассмотрим коллектив из пяти роботов (
n =
5).
Каждый
робот должен переместиться в одну из трех заданных целевых точек
(
m =
3).
Известно требуемое количество роботов для каждой целевой
точки (ЦТ):
n
1
= 2,
n
2
= 1,
n
3
= 2. Необходимо распределить целевые
точки таким образом, чтобы каждый робот при перемещении в вы-
бранную точку стремился пройти как можно меньшее расстояние,
учитывая интересы других роботов. Расстояния между роботами и
целевыми точками известны.
В данном случае «стоимость»
C
ij
–
это расстояние между
i
-
м ро-
ботом и
j
-
й целевой точкой, где
i
= 1, …, 5,
j
= 1, …, 3. Ценовые мас-
сивы роботов приведены в табл. 4.
Таблица 4
Ценовые массивы роботов
Робот 1
Робот 2
Робот 3
Робот 4
Робот 5
ЦТ «Цена» ЦТ «Цена» ЦТ «Цена» ЦТ «Цена» ЦТ «Цена»
1
4
1
2
1
3
1
4
1
6
2
1
2
5
2
4
2
2
2
4
3
6
3
3
3
5
3
3
3
2