Консенсус и кооперация в сетевых многоагентных системах

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