=Paper=
{{Paper
|id=Vol-1787/512-517-paper-89
|storemode=property
|title=Распределенная модель бактериального поиска на основе марковских клеточных автоматов (Distributed model of bacterial foraging algorithm based on Markov cellular automata)
|pdfUrl=https://ceur-ws.org/Vol-1787/512-517-paper-89.pdf
|volume=Vol-1787
|authors=Nikolay Ershov,Sergey Poluyan
}}
==Распределенная модель бактериального поиска на основе марковских клеточных автоматов (Distributed model of bacterial foraging algorithm based on Markov cellular automata)==
https://ceur-ws.org/Vol-1787/512-517-paper-89.pdf
Распределенная модель бактериального поиска
на основе марковских клеточных автоматов
Н. М. Ершов1,а, С. В. Полуян2,b
1
Московский государственный университет им. М. В. Ломоносова,
119991, Москва, ГСП-1, Ленинские горы, д. 1, стр. 52
2
ГБОУ ВО Московской области "Университет "Дубна"
141980, Московская область, г. Дубна, ул. Университетская, 19
E-mail: a ershov@cs.msu.ru, b svpoluyan@gmail.com
Групповая робототехника представляет собой перспективное направление в области роевого интел-
лекта, заключающееся в построении робототехнических систем, состоящих из большого числа относи-
тельно просто устроенных роботов. Актуальной задачей в этой области является разработка распреде-
ленных алгоритмов управления такого рода системами. Проблема заключается в том, что требуется раз-
работать алгоритм решения некоторой глобальной задачи, недоступной отдельным роботам,
программируя локальное поведение многих таких роботов, действующих параллельно. В настоящей ра-
боте в качестве инструмента разработки такого рода распределенных алгоритмов предлагается использо-
вать стохастические блочные клеточные автоматы с Марковскими системами правил. В таких автоматах
каждая клетка помимо состояния, которое кодируется некоторым символом, обладает также ориентаци-
ей. Обновление состояния автомата выполняется посредством вероятностного разбиения множества его
клеток на символьные цепочки с учетом ориентации клеток и последующей замене этих подцепочек со-
гласно заданной системе правил. Особенностью предлагаемого подхода является то, что он позволяет
единообразно описать как алгоритмическое поведение самих роботов, так и возможно неупорядоченное
поведение среды. В работе рассматривается процесс разработки колонии искусственных бактерий, вы-
полняющих коллективный поиск питательных веществ. За основу поведенческой модели бактерий был
выбран алгоритм бактериального поиска – уже классический алгоритм роевой оптимизации, хорошо за-
рекомендовавший себя при решении различных задач непрерывной и дискретной оптимизации. В работе
описывается клеточно-автоматная организация искусственных бактерий, предлагается реализация ос-
новных механизмов поведения бактерий – движение, рост, деление, смерть. Особое внимание уделяется
построению механизма управления движением бактерий под действием химических сигналов – хемотак-
сису бактерий, играющего центральную роль в алгоритме бактериального поиска. Приводятся результа-
ты компьютерного моделирования и численных экспериментов, показывающие работоспособность, как
построенных распределенных алгоритмов управления колонией искусственных бактерий, так и всего
клеточно-автоматного подхода к созданию такого рода алгоритмов.
Ключевые слова: роевой интеллект, роевая робототехника, бактериальный поиск, популяционное
моделирование, клеточные автоматы
Работа выполнена при финансовой поддержке РФФИ (грант № 14-07-00628 А).
© 2016 Николай Михайлович Ершов, Сергей Владимирович Полуян
512
Введение
Групповая робототехника представляет собой перспективное направление в области рое-
вого интеллекта, заключающееся в построении робототехнических систем, состоящих из боль-
шого числа относительно просто устроенных роботов [Brambilla, Ferrante, …, 2013]. Актуаль-
ной задачей в этой области является разработка распределенных алгоритмов управления такого
рода системами. В настоящей работе в качестве инструмента разработки такого рода распреде-
ленных алгоритмов предлагается использовать стохастические блочные клеточные автоматы с
Марковскими системами правил [Ershov, Кравчук, 2015]. Особенностью такого подхода явля-
ется то, что он позволяет единообразно описать как алгоритмическое поведение самих роботов,
так и возможно неупорядоченное поведение среды. В работе рассматривается процесс разра-
ботки колонии искусственных бактерий, выполняющих коллективный поиск питательных ве-
ществ, при этом, особое внимание уделяется построению механизма управления движением
бактерий под действием химических сигналов – хемотаксису бактерий [Passino, 2002].
Структура клеточно-автоматной модели бактерии
Задана двумерная прямоугольная область, в каждой клетке которой располагается ровно
–
один символ из алфавита A. Кроме того, каждая клетка обладает некоторой ориентацией, т.е. ей
приписано одно из четырех направлений вправо (E), влево (W), вверх (N) и вниз (S). Будем
считать, что пустые клетки автомата содержат «пустой» символ . Эволюция клеточного авто-
мата происходит по следующей схеме. В начальный момент времени задается начальное рас-
пределение символов в форме символьной матрицы X, с элементами из алфавита A и начальное
распределение направлений в форме матрицы D с символами из алфавита {E, W, N, S}. На каж-
дом шаге алгоритма происходит модификация этих матриц в два этапа.
На первом этапе клетки матрицы X перебираются в случайном порядке. Если текущая
клетка еще не была рассмотрена, то с вероятностью к ней присоединяется соседняя клетка, на
которую указывает соответствующий символ матрицы D (если эта клетка еще свободна). В ре-
зультате такого процесса матрица X разбивается на некоторое количество символьных цепочек.
Пример такого разбиения показан на рисунке 1, начальные клетки в цепочках выделены чер-
ным цветом стрелок.
Рис. 1. Процесс разбиения клеточного пространства на символьные цепочки
На следующем этапе к каждой из полученных цепочек применяется правило из –системы
правил данного клеточного автомата. Каждое правило имеет вид [p], где и две це-
почки символов из алфавита A одинаковой длины, p вероятность применения данного правила
–
(по умолчанию p = 1). При этом каждый символ в цепочке может быть помечен одним из мо-
дификаторов, которые указывают, как должна поменяться ориентация соответствующей клет-
ки. Например, модификатор «*» определяет случайное изменение ориентации. Модификатор-
цифра меняет ориентацию данного символа на ориентации символа с указанным номером, к о-
торой последний обладал до применения этого правила. –
Все пространство клеточного автомата условно разделяется на две части на бактерии и
на окружающую их среду. Будем предполагать, что среда представляется пустыми символами
и рассматривается в качестве пространства, в котором перемещаются бактерии. Сами бактерии
513
представляются одномерными цепочками символов, в которых каждый символ (кроме послед-
него) ориентированы на следующий за ним символ. В базовом состоянии первая клетка цепоч-
ки, представляющей бактерию, содержит символ t (tail), последняя клетка цепочки – символ h
(head), а все остальные внутренние клетки цепочки – символы x. Пример клеточного автомата с
одной бактерией приведен на рисунке 2.
Рис. 2. Клеточно-автоматное устройство бактерии
Такая организация бактерий (с учетом описанной выше схемы разбиения клеточного про-
странства на одномерные цепочки) позволяет сделать все клетки бактерии (кроме головной
клетки) недоступными для внешней среды. Все взаимодействие бактерии с внешней средой
будет тогда производиться только со стороны (и с непосредственным участием) головного сим-
вола этой бактерии.
Реализация базовых типов поведения бактерий
Простейшим взаимодействием бактерии со средой является ее движение в пространстве,
представленным этой средой. Схема прямолинейного движения бактерии описывается сле-
дующей системой правил:
ℎ → ℎ ,
→ ,
→ ,
→ .
Первое правило системы описывает процесс перемещения головы бактерии на свободную
–
клетку перед ней. Символ m соответствует растяжению бактерии и по правилам 2 3 этот сим-
вол постепенно перемещается к хвосту бактерии. Последнее правило перемещает хвост t на од-
ну позицию и высвобождает пустой символ . Если к системе правил движения добавить пра-
вило h h *, приводящее к случайному изменению ориентации головного символа, то бактерия
начнет двигаться по случайной траектории.
Рис. 3. Движение и рост бактерии
Будем представлять питательные вещества символами a. Эти символы будут совершать
случайные блуждания, которые описываются следующей системой правил: a а*, a a *.
Процесс потребления питательных символов бактериями в простейшем варианте описывается
одним правилом ha xh*, т.е. бактерия потребляет символ a, который тут же превращается во
внутренний символ x, что приводит к росту бактерии. На рисунке 3 показан пример одновре-
менного движения и роста одной бактерии.
514
Можно считать, что символы x представляют собой некоторую накопленную бактерией
энергию. И эта энергия должна расходоваться на поддержание ее жизнедеятельности. Про-
стейший вариант такого процесса расходования энергии может быть представлен одним прави-
лом вида tx t, срабатывание которого приводит к уничтожению одного символа x. Варьируя
вероятность p в этом правиле, можно менять скорость расходования накопленных питательных
символов a – чем больше p, тем быстрее тратятся символы x, тем быстрее укорачивается бакте-
рия.
Если длина бактерии уменьшается до 2 (цепочка th), то бактерия становится неактивной
(она не может ни двигаться, ни питаться). В этом случае можно явно завершить ее существова-
ние правилом th . Таким образом, при отсутствии достаточного количества питательных
веществ в окружающей среде бактерии постепенно вымирают. Если же питательных веществ в
окружающей среде достаточно много, то длина бактерии будет неограниченно возрастать. Что-
бы предотвратить такое развитие событий, можно ввести в рассмотрение деление бактерии на
две новые бактерии при достижении ею некоторой критической длины.
Рис. 4. Пример развития популяции бактерий
Этот процесс можно запрограммировать следующим образом. Символ t (хвост) с вероятно-
стью p1 генерирует сигнальный символ s: tx ts, который перемещается по направлению к го-
ловному символу: sx xs, sm ms. Этот символ, в свою очередь, с вероятностью p2 вызывает
деление бактерии в том месте, где он находится в данный момент времени: sx ht. Чем длин-
нее бактерия, тем больше вероятность, что она будет поделена на две новые бактерии. Пример
развития популяции с одной бактерией в начальный момент времени приведен на рисунке 4.
Хемотаксис бактерий
Под хемотаксисом бактерий понимается некоторый адаптивный механизм движения бак-
терий, учитывающий тем или иным способом концентрацию химических веществ (питатель-
ных веществ или репеллентов) в окружающей бактерию среде. Известно, что многими видами
бактерий реализуется т.н. градиентный механизм хемотаксиса, когда тип движения бактерий
(прямолинейное движение или хаотическое движение) определяется по градиенту изменения,
например, полезных веществ. Если их концентрация растет, то бактерия совершает более дол-
гие прямолинейные движения. Если же эта концентрация начинает падать, то бактерия перехо-
дит к хаотическому движению.
В настоящей работе был реализован более простой «пороговый» вариант хемотаксиса. В
этом случае бактерия также выбирает между двумя указанными выше типами движения, но
теперь этот выбор производится на основании текущей концентрации питательных веществ, а
не на ее градиенте. Если уровень концентрации высокий, то бактерия находится в «хорошем»
месте, поэтому она переходит к хаотическому движению, которое не позволяет бактерии быст-
ро удалиться от текущего ее положения. Если же уровень концентрации низкий, то бактерии
надо как можно быстрее покинуть это место. Для этого бактерия просто переходит к прямоли-
нейному движению в случайно выбранном направлении. Отметим, что «прямолинейность»
515
движения в данном случае означает, что бактерия относительно редко (по отношению к хаоти-
ческому режиму) меняет направление своего движения.
Была выполнена реализация такого механизма. Чтобы протестировать его работоспособ-
ность, была рассмотрена разновидность бактерий, которые не растут, не укорачиваются, не де-
лятся и не умирают. Потребление питательных веществ, таким образом, не приводит к удлине-
нию бактерий, а влияет только на способ их движения. В проведенном численном эксперимен-
те в центре поля располагался «генератор питательных веществ», который с высокой частотой
производит питательные символы, совершающих в дальнейшем случайные блуждания. Таким
образом, концентрация питательных веществ оказывается тем выше, чем ближе текущая точка
к источнику пищи. Всего в системе присутствовало 50 бактерий, которые в начальный момент
времени были распределены равномерно по клеточному пространству.
Рис. 5. Уменьшение расстояния до источника пищи под действием «порогового» хемотаксиса
На рисунке 5 показано, как изменяется среднее расстояние (среди всех бактерий) до источ-
ника пищи в процессе эволюции автомата. Прямая линия соответствует среднему расстоянию
до источника пищи при случайном расположении бактерий. Видно, что постепенно все боль-
шее число бактерий начинает концентрироваться в окрестности источника пищи.
Таким образом, проведенные численные исследования показали, что описанный механизм
порогового хемотаксиса является вполне работоспособным. Его эффективность, скорее всего,
будет более высокой, если одновременно с ним использовать механизм отбора, основанный на
росте бактерий и их делении при высокой концентрации пищи, а также укорачивания и смерти
при недостатке пищи.
Список литературы
Brambilla M., Ferrante E., Birattari M., Dorigo M. Swar m robotics: a review from the swarm engi-
neering perspective // Swarm Intelligence. 2013. Vol. 7, No. 1. P. 1 41.
Ершов Н.М., Кравчук А.В. Дискретное моделирование с помощью стохастических клеточных
автоматов // Вестник Российского университета дружбы народов: Серия Математика, ин-
форматика, физика. 2015. № 2. С. 359 362.
Ershov N.M., Kravchuk A.V. Diskretnoe modelirovanie s pomoschyu stohasticheskikh kletochnykh avtomatov [Dis-
crete Modeling Using Stochastic Cellular Automata] // Vestnik Po ssijskogo universiteta druzhby narodov: Seriya
Mathematika, informatika, fizika [Bulletin of Peoples’ Friendship University of Russia. Series Mathematics. Infor-
mation Sciences. Physics]. 2015. No. 2. P. 359 362 (in Russian).
Passino K.M. Biomimicry of bacterial foraging for distributed optimization and control // IEEE Con-
trol Systems Magazine. — 2002. — Vol. 22, No. 3. — P. 52– 67.
516
Distributed model of bacterial foraging algorithm
based on Markov cellular automata
N. M. Ershov1,a, S. V. Poluyan2,b
1
Lomonosov Moscow State University,
1-52, Leninskiye Gory , GSP-1, Moscow, 119991, Russia
2
Moscow Region State Educational Institution for higher professional education University “Dubna”
19, Universitetskaya str., Dubna, Moscow region, 141980, Russia
E-mail: a ershov@cs.msu.ru , b svpoluyan@gmail.com
Swarm robotics is a new approach to the coordination of multi robot systems which consist of large num-
bers of mostly simple physical robots. It is supposed that a desired collective behavior emerges from the interac-
tions between the robots and interactions of robots with the environment. An actual problem in this field is the
development of the distributed algorithms for managing this kind of systems. Such kind of algorithms should
solve a global problem, which is not available to individual robots, by programming the local behavior of many
such robots operating in parallel. In this paper we propose to use stochastic block cellular automata as tool for
the development of such distributed algorithms. In such automata every cell in addition to symbolic state has
also orientation to one of its nearest neighbors. Updating the state of the automaton is performed by using proba-
bilistic partition of its cells to the character chains, based on the orientation of the cells, and subsequent replace-
ment of these chains according to a predetermined system of rules. A special feature of suggested approach is
that it allows to uniformly describe both the algorithmic behavior of the robots themselves and disorderly behav-
ior of the environment. The paper deals with the process of the development of artificial colony of bacteria that
perform a collective search for nutrients. Used behavioral model of bacteria is based on the bacterial search algo-
rithm, which is a classic swarm optimization algorithm, well-proven in solving various problems of continuous
and discrete optimization. The paper describes the cellular automaton organization of artificial bacteria, suggest-
ed implementation of the major mechanisms of bacterial behavior – movement, growth, division and death. Par-
ticular attention is paid to the construction of moving control mechanism of bacteria under the influence of
chemical signals – bacterial chemotaxis, which plays a central role in bacterial foraging algorithm. The results of
computer modeling and numerical experiments are described, which show the performance as proposed distrib-
uted algorithms of controlling artificial colony of bacteria and the entire cell-automata approach to the creation
of such algorithms.
Keywords: swarm intelligence, swarm robotics, bacterial foraging algorithm, population-based modeling,
cellular automata
The work was supported by Russian Foundation for Basic Research (RFBR Project 14-07-00628).
© 2016 Nikolay M. Ershov, Sergey V. Poluyan
517