Как сделать робота с поведением, основанным на цепи Маркова

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

Поисковое поведение и цепь Маркова

Если внимательно понаблюдать за тем, как бегает муравей или какая-нибудь букашка, то можно заметить, что они никогда не двигаются по прямой постоянно (даже, когда муравей бежит по феромоновому следу). В процессе своего движения они так или иначе осуществляют поисковое поведение. Простым вариантом поисковой стратегии является случайное блуждание. Модель такого поведения можно реализовать построив цепь Маркова – математическую систему, в которой переход в одно из возможных следующих состояний зависит от того, в каком состоянии система находится в данный момент, и происходит по определённым вероятностным правилам.

Цепи Маркова (Markov chains, MC либо discrete time Markov Chains, DTMC) являются предшественниками сетей Хопфилда и машин Больцмана. Понятие марковской цепи принадлежит выдающемуся русскому математику Андрею Андреевичу Маркову, работавшему в области вероятностных процессов, теории чисел и математической статистики. В своих статьях, опубликованных в 1906-1908 гг, Марков описал математические модели для решения ряда лингвистических проблем. С тех пор они нашли широкое применение в различных областях, таких как машинное обучение, генерация текстов, криптография, статистическое моделирование для широкого спектра явлений реального мира. На марковских цепях во многом основывается ранжирование страниц в поисковых системах.

Одно из приложений цепей Маркова в нейронных сетях, которое многие из нас используют ежедневно, – функция предугадывания ввода текста на мобильных устройствах. Вы наверняка замечали, что предсказание следующего слова становится «умнее» по мере того, как вы больше пользуетесь телефоном, в конечном итоге предлагая слова, которые являются уникальными для вас и ваших текстов. Это происходит потому, что программное обеспечение постепенно выстраивает цепь Маркова на основе ваших шаблонов набора текста и вычисляет вероятность следующего набранного вами слова на основе того, что вы уже набрали.

Марковскую цепь можно представить в виде графа, на котором вершинами будут состояния, в которых находится система, а ребрами – возможные варианты перехода в другие состояния. На ребрах записывают вероятности таких переходов. Кроме того, каждое состояние марковской цепи можно представить вектором-строкой — распределением вероятностей перехода в другие состояния. Набор таких векторов может быть собран в матрицу вероятностей переходов, с которой удобно работать программно. На рисунке показан пример цепи Маркова с двумя состояниями (A и B), представленной в виде графа и матрицы вероятностей переходов. Матрица переходов составлена из вектора-строки распределения вероятностей переходов из A в A и B (0.7, 0.3) и вектора-строки распределения вероятностей переходов из B в A и B (0.6, 0.4). То есть, если мы находимся в состоянии A, то вероятность снова перейти в состояние A равна 70%, а вероятность перейти в состояние B – 30%. В следующий момент времени, если мы находимся в состоянии B, то вероятность снова перейти в состояние B равна 40%, а перейти в состояние A – 60%.

Давайте попробуем сделать простого робота, реализующего поведение, основанное на цепи Маркова. Но прежде, чем мы приступим к созданию математической части и программы, давайте рассмотрим, как сделать техническую часть робота.

Что нам понадобится?

• плата ESP32 DEVKIT V1
• драйвер двигателей L293D
• две макетные платы
• отсек для четырех батареек AA
• соединительные проводники
• два мотора FA-130 3-6 В с редуктором и колесами
• подруливающее колесо или опора скольжения
• конструктив для изготовления платформы робота

Схема робота

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

Для управления моторами с помощью ESP32 будем использовать, например, выводы платы микроконтроллера D25, D26, D32 и D33. Для левого мотора — D32, D26, для правого — D33, D25.

Подробнее об управлении моторами с помощью микросхемы драйвера двигателей L293D можно прочитать на странице "ESP32: Управление мотором".





Электролитический конденсатор C1 необходим для того, чтобы сгладить броски по питанию, вызванные работой моторов. При сборке схемы этот конденсатор следует располгать в непосредственной близости к выводу Vs микросхемы драйвера моторов.

Монтаж схемы робота можно сделать на двух макетных платах с использованием проводов-перемычек. Обратите внимание, что красный провод питания, идущий от отсека с батареями, подключен в непосредственной близости от вывода для питания моторов микросхемы L293D.

Граф цепи Маркова для робота

Начнем с того, что определимся с набором состояний, в которых может находиться наш робот. Начнем с самых простых: движение вперед, движение назад, поворот вправо, поворот влево, стоп. Нарисуем пять вершин для этих состояний. От каждой вершины нарисуем стрелки-ребра к другим вершинам, которые будут обозначать переходы от одного состояния к другому. Переходы между вершинами "Вперед" и "Назад" рисовать не будем, так как такое изменение движения может выглядеть не очень естественно. Также из каждой вершины нарисуем круговую стрелку, направленную к самой этой вершине. Эти стрелки будут обозначать, что из каждого состояния может произойти переход в это же состояние.

После того, как граф состояний будет готов, необходимо разметить его переходными вероятностями. Значение вероятности для каждого из переходов напишем на ребрах графа. Для состояния "Вперед" вероятности переходов могут быть следующие: продолжить движение вперед – 0.4, сделать поворот влево – 0.25, сделать поворот вправо – 0.25, остановиться – 0.1. Вероятности могут быть и другими, но сумма всех вероятностей всегда должна быть равна 1 для любой из вершин.

Назначим вероятности для всех ребер графа. В результате может получиться что-то подобное:


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

Матрица вероятностей переходов

Матрицу можно построить и без предварительного рисования графа. Мы построим матрицу для робота, записывая значения вероятностей в процентах. Такая запись будет удобнее для восприятия. Еще раз отметим, что сумма значений каждой строки должна быть равна 100%.

Текущее состояние	Вероятность перехода (%)
	F	L	R	B	S
F	40	25	25	0	10
L	39	29	8	12	12
R	39	8	29	12	12
B	0	27	27	26	20
S	22	26	26	20	6

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



С помощью генератора случайных чисел получим случайное значения в диапазоне от 1 до 100. Допустим, выпало 52. Это значение находится перед отметкой 65 и попадает в состояние L (Left).

Попробуем переписать первую строку матрицы следующим образом:

F

40

65

90

90

100

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

Переписав все строки подобным образом, получим таблицу, с которой будет удобно работать в программе.

	F	L	R	B	S
F	40	65	90	90	100
L	39	68	76	88	100
R	39	47	76	88	100
B	0	27	54	80	100
S	22	48	74	94	100

Программа для управления роботом с помощью цепи Маркова

Для реализации программы нам понадобится класс Pin, функция задержки sleep и функция randint для генерации случайных чисел.

from machine import Pin # из модуля machine импортируем класс Pin
from time import sleep # из модуля time импортируем функцию sleep
from random import randint # из модуля random импортируем функцию randint

У нашего робота существует пять состояний. Создадим для реализации каждого состояния отдельную функцию. Назовем их forward, backward, left, right, stop. Время задержек в функциях sleep приводится для популярных мотор-редукторов, описанных в статье "ESP32: УПРАВЛЕНИЕ МОТОРОМ", и колес диаметром 65 мм.

def forward(): # функция для движения вперед
    motor_pin1.value(0); motor_pin2.value(1) # правый мотор вперед
    motor_pin3.value(0); motor_pin4.value(1) # левый мотор вперед
    sleep(1)
def backward(): # функция для движения назад
    motor_pin1.value(1); motor_pin2.value(0) # правый мотор назад
    motor_pin3.value(1); motor_pin4.value(0) # левый мотор назад
    sleep(1) 	
def right(): # функция для поворота вправо
    motor_pin1.value(1); motor_pin2.value(0) # правый мотор назад
    motor_pin3.value(0); motor_pin4.value(1) # левый мотор вперед   
    sleep(0.5)
def left(): # функция для поворота влево
    motor_pin1.value(0); motor_pin2.value(1) # правый мотор вперед
    motor_pin3.value(1); motor_pin4.value(0) # левый мотор назад   
    sleep(0.5)
def stop(): # функция для остановки
    motor_pin1.value(0); motor_pin2.value(0) # правый мотор стоп
    motor_pin3.value(0); motor_pin4.value(0) # левый мотор стоп    
    sleep(1) 

Для управления моторами нам понадобится создать объекты Pin, которые используются в функциях, описанных выше.

# правый мотор
motor_pin1 = Pin(25, Pin.OUT)
motor_pin2 = Pin(33, Pin.OUT)
# левый мотор
motor_pin3 = Pin(26, Pin.OUT)
motor_pin4 = Pin(32, Pin.OUT)

Для удобного переключения состояний создадим словарь actions с названиями наших функций. Ключами сделаем числа 0, 1, 2, 3, 4.

actions = {0:forward, 1:left, 2:right, 3:backward, 4:stop}

Создадим переменную state для хранения текущего состояния и дадим ей начальное значение 0, соответствующее движению вперед (forward).

Создадим список с матрицей вероятностей переходов.

m = [[40, 65, 90, 90, 100],
     [39, 68, 76, 88, 100],
     [39, 47, 76, 88, 100],
     [ 0, 27, 54, 80, 100],
     [22, 48, 74, 94, 100]]

В бесконечном цикле будем генерировать случайное число от 1 до 100 для выбора следующего состояния. После этого в цикле будем проходиться по строке матрицы, соответствующей текущему состоянию, и проверять, меньше или равно сгенерированное число перебираемым значениям из строки матрицы. Как только мы найдем подходящее значение в строке, его индекс i и будет номером следующего состояния для робота (присвоим переменной state текущее значение i и прервем цикл for с помощью break). Зная номер следующего состояния, запустим соответствующую номеру функцию из созданного нами словаря командой actions[state]().

while True:
    rnd = randint(1, 100) # генерируем случайное число
    for i in range(5): # цикл для перебора значений из матрицы
        if rnd <= m[state][i]: # сравниваем сгенерированное значение
            state = i # запоминаем новое состояние
            break # выходим из цикла
    actions[state]() # запускаем функцию для нового состояния

Полный текст программы для робота на языке MicroPython может выглядеть следующим образом:

from machine import Pin # из модуля machine импортируем класс Pin
from time import sleep # из модуля time импортируем функцию sleep
from random import randint # из модуля random импортируем функцию randint
    
def forward(): # функция для движения вперед
    motor_pin1.value(0); motor_pin2.value(1) # правый мотор вперед
    motor_pin3.value(0); motor_pin4.value(1) # левый мотор вперед
    sleep(1)
def backward(): # функция для движения назад
    motor_pin1.value(1); motor_pin2.value(0) # правый мотор назад
    motor_pin3.value(1); motor_pin4.value(0) # левый мотор назад
    sleep(1) 	
def right(): # функция для поворота вправо
    motor_pin1.value(1); motor_pin2.value(0) # правый мотор назад
    motor_pin3.value(0); motor_pin4.value(1) # левый мотор вперед   
    sleep(0.5)
def left(): # функция для поворота влево
    motor_pin1.value(0); motor_pin2.value(1) # правый мотор вперед
    motor_pin3.value(1); motor_pin4.value(0) # левый мотор назад   
    sleep(0.5)
def stop(): # функция для остановки
    motor_pin1.value(0); motor_pin2.value(0) # правый мотор стоп
    motor_pin3.value(0); motor_pin4.value(0) # левый мотор стоп    
    sleep(1)  

# Объекты Pin для правого мотора
motor_pin1 = Pin(25, Pin.OUT)
motor_pin2 = Pin(33, Pin.OUT)
# Обекты Pin для левого мотора
motor_pin3 = Pin(26, Pin.OUT)
motor_pin4 = Pin(32, Pin.OUT)

# словарь с названиями функций движения
actions = {0:forward, 1:left, 2:right, 3:backward, 4:stop}
# инициализация переменной состояний
state = 0

# Матрица вероятностей переходов
m = [[40, 65, 90, 90, 100],
     [39, 68, 76, 88, 100],
     [39, 47, 76, 88, 100],
     [ 0, 27, 54, 80, 100],
     [22, 48, 74, 94, 100]]

while True: # бесконечный цикл
    rnd = randint(1, 100) # генерируем случайное число
    for i in range(5): # цикл для перебора значений из матрицы
        if rnd <= m[state][i]: # сравниваем сгенерированное значение
            state = i # запоминаем новое состояние
            break # выходим из цикла
    actions[state]() # запускаем функцию для нового состояния

Запустим Iguana IDE – среду программирования для MicroPython. Скопируем в нее текст программы. Подключимся к микроконтроллеру с помощью USB-кабеля или по Wi-Fi и загрузим программу в микроконтроллер.



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

Чтобы сделать робота еще более "живым", можно поэкспериментировать с цепью Маркова. Изменение вероятностей переходов даже на несколько процентов может достаточно сильно изменить общее поведение.

Также можно добавить дополнительные состояния. Интересным вариантом может быть использование следующей функции, которую можно назвать, например, shakey (в честь знаменитого стэнфордского интегрального робота Шейки — первого мобильного робота, управляемого искусственным интеллектом):

def shakey():
    for i in range(4):
        left()
        sleep(0.1)
        right()
        sleep(0.1)

Эта функция реализует быстрые повороты из стороны в сторону, что можно ассоциировать с вилянием хвостом или отряхиванием у животных.

Полеты Леви

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

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

В отличие от простого случайного блуждания, где объект может многократно возвращаться в одно и то же место, более сложные модели требуют сочетания последовательностей коротких шагов с редкими перемещениями на большие расстояния. Например, в своей работе, опубликованной в 1949 году, советские математики Борис Гнеденко и Андрей Колмогоров разработали модель, которая позволяет объяснить феномен супер-диффузии. Они выяснили, что устойчивые распределения, выявленные французским математиком Полем Пьером Леви в 1937 году, и супер-диффузия взаимосвязаны. В своей книге «Фрактальная геометрия природы», выпущенной в 1982 году, Бенуа Мандельброт назвал эту модель случайного блуждания, основанную на направленных длинных участках движения, термином «полеты Леви».

В 1986 году физики Майкл Ф. Шлезингер из США и Джозеф Клафтер из Израиля стали одними из первых, кто выдвинул гипотезу о том, что модели движения живых организмов могут демонстрировать блуждания Леви. Они показали, что такое поведение может оказаться выгодным при поиске пищи, укрытия или более благоприятных условий среды, поскольку это позволяет избежать ненужного возвращения на уже исследованные территории. В результате, организмы адаптируются лучше с точки зрения естественного отбора. Кроме того, авторы предположили, что блуждания Леви могут представлять собой врожденную и эволюционно закрепленную оптимальную стратегию поиска.

В 1996 году статья Гандхимохана Вишванатана произвела революцию в понимании поискового поведения животных. Вишванатан, анализируя траектории полета альбатросов в поисках пищи над поверхностью океана, обнаружил поразительную закономерность: их маршруты демонстрировали инвариантность траекторий относительно масштаба рассмотрения. Это означает, что независимо от того, рассматриваем ли мы полёт на протяжении нескольких часов или нескольких дней, общая структура траектории остаётся схожей – похожей на "фрактал" – самоподобной фигурой, детали которой повторяются в разных масштабах. Более того, продолжительность отдельных этапов полёта альбатроса подчинялась степенному закону, что указывало на неслучайность и определённую стратегию поиска. Вместо случайного блуждания, характеризующегося равномерным распределением длин перемещений, траектории альбатросов демонстрировали чередование коротких и длинных перелётов.

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

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

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

Удачный Вам экспериментов!

См. также:

ESP32: Управление мотором

Подключение ультразвукового датчика расстояния HC-SR04

ESP32: Используем АЦП (ADC) для измерения аналогового сигнала