Программирование: события и состояния

Что, в общих словах, можно сказать про робота, который выполняет какую-то программу? Если, например, в момент начала наблюдения, робот едет? Ответ, лежащий на поверхности, – робот двигается. Но, очевидно, этот же ответ не подойдет как общий для того момента времени, когда робот стоит.

Поэтому, неплохим вариантом становится фраза "робот находится в каком-то состоянии". Так, к примеру, можно заявить, что робот находится в состоянии движения или состоянии остановки, можно даже разделять состояние выполнения поворота от простого движения.

Таким образом, поведение робота – это череда его состояний. Например, движение по квадрату – сначала робот в состоянии движения прямо, затем, в состоянии поворота налево, которое сменяется опять, состоянием движения прямо и т.д.


Что заставляет робота изменить свое состояние? Если рассматривать пример про движение по квадрату, то смена одного состояния на другое происходит после прохождения всем роботом определенной дистанции, в случае движения прямо, или после прохождения определенной дистанции одним колесом, в случае поворота. Здесь, в обоих случаях, пройденная дистанция определяется сенсором поворота оси двигателя. Иначе можно сказать, что робот сменил направление движения (состояние) после наступления определенного события на сенсоре поворота, в данном случае событие – сигнал от сенсора о достижении определенного угла поворота оси.

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

Как же эта диаграмма будет отображена в программу на NXT-G? Например, так:

Как видно, программа состоит из блоков движения. Но где же тогда в данной программе обработчики событий?
Дело в том, что каждый блок движения, в котором явно задается количество необходимого движения в градусах, поворотах или секундах, содержит уже обработчик, направленный на определение возникновения перечисленных выше событий:

Иначе, такой блок можно было бы описать целой последовательностью:
"Ехать бесконечно до тех пор, пока ось мотора не сделает поворот в 720 градусов":

Или более сложный вариант, раскрывающий, что же действительно подразумевается под блоком "Wait":

Как показывает этот довольно простой пример, даже самая простая программа состоит из череды состояний и ожиданий событий. Любая.
Будь то просто вывод на экран: состояние вывода на экран букв текста, пока не наступит событие "конец текста", или сложная программа игры в крестики-нолики.

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

Тогда блок "Выполнить ход робота", возможно представить в виде подблоков:

Здесь, уже каждый подблок может быть представлен в виде конкретных действий языка NXT-G.

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

Как видно из схемы, существуют три разных события, на которые может реагировать робот в состоянии движения прямо:

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

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

Давайте рассмотрим алгоритм движения вдоль стены, предложенный в Задаче #1, с точки зрения того, из каких состояний он состоит, и какие события там влияют на переключение этих состояний.

В алгоритме два состояния (поворот налево и поворот направо) сменяют друг друга, как реакция на события приходящие от сенсора расстояния.



Реализация его на NXT-G будет следующая.

Словами программу можно описать следующим образом: 

1. "Бесконечно" выполняем поворот налево до тех пор, пока сенсор не вернет расстояние до препятствия меньше 14 сантиметров.
2. Меняем направление поворота и "бесконечно" выполняем поворот направо до тех пор, пока сенсор не вернет расстояние до препятствия больше 16 сантиметров.
3. Снова переходим к первому действию, тем самым, выполняя повороты друг за другом в цикле.

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

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

Таким образом, с точки зрения программы, вводится еще одно состояние – движение прямо. И как в этом случае, выглядит диаграмма переходов?


Еще даже до написания программы на NXT-G, необходимо указать на очевидные недостатки именно этой реализации:

1. Движение начинается с того, что мы едем прямо до тех пор, пока расстояние до препятствия не станет меньше 14 см. А что, если при этом робот наоборот удаляется от стены? Расстояние никогда не уменьшиться до необходимого, и робот никогда не перейдет к другому шагу.
2. А если на первое место поставить движение от стены, пока не станет больше 16 см? То робот, в случае его изначальной ориентации в сторону стены, опять же будет бесконечно приближаться к ней, пока не столкнется.
3. Если поменять характер движения, так что робот будет начинать движение с поворота, противоречит введенному изначально подходу – ехать прямо там, где это возможно. Если изначально робот установлен параллельно стене на нужном расстоянии, что вполне вероятно, самым первым движением робот выводит себя из этого состояния. После чего вынужден будет бесконечно пытаться обрести его.
4. Из-за низкой точности сенсора расстояния, робот будет некорректно реагировать на очень близкие друг к другу показания сенсора: 14 и 15 см., 15 и 16 см.
5. Наконец, если рассматривать код с точки зрения красоты, то два одинаковых действия "движения вперед" отрицательно сказываются на этом параметре.

Тем не менее, новая программа будет выглядеть следующим образом:

Давайте попробуем избавиться хотя бы от части найденных недостатков. Для этого:

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

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

Тогда реализация на NXT-G будет следующая:

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

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

Схема очень похожа на самую первую реализацию, от которой мы начали отталкиваться. Соответственно, она наделена теми же недостатками – при попытке добавить новое действие с реакцией на новое событие, скорее всего, опять возникнет проблема, в какое место в программе это новое ожидание поместить, чтобы программа сохраняла свою работоспособность.
Например, что если заменить поворот несколькими видами: плавный поворот и крутой поворот. И так и для левого и для правого поворота.

При расстоянии до стены меньше 12 см. робот должен делать крутой поворот вправо, при расстоянии от 12 до 14 см. робот должен делать плавный поворот вправо, при расстоянии 14 до 16 см. он должен ехать прямо, при данных сенсора от 16-18 см. выполняется плавный поворот влево, а если робот находится больше, чем 18 см. от стены, крутой поворот влево должен исправить эту ситуацию.

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

Иными словами, диаграмма переходов состояний в таком случае будет следующая:

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

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

В этом случае получается, что работу робота можно описать следующим образом:

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

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

• Event=0 – на сенсоре >14 см., но <16 см.
• Event=1 – на сенсоре <12 см.
• Event=2 – на сенсоре >12 см., но <14 см.
• Event=3 – на сенсоре >16 см., но <18 см.
• Event=4 – на сенсоре >18 см.

Т.е. если в блоке распознавания события обнаружится, что сенсор показывает значение больше 12 см., но меньше 14 см., он передаст в следующий блок значение "2". А блок выборки и выполнения действия знает, что если к нему пришло значение "2", нужно запустить плавный поворот вправо.

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

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

2 события – 2 поворота:


3 события – 2 поворота и движение прямо:


5 событий – 2 крутых поворота, 2 плавных и движение прямо:


Из этих примеров хорошо видно, что сложность алгоритма движения растет, в то время как сложность программы практически нет.

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

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

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

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



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


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


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

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

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


От предыдущей диаграммы ее отличает

1. Появление новой сущности – состояние. Состояние, определенное после одной итерации, используется как входные данные для определения нового действия и нового состояния.
2. Отдельные блоки для выбора действия и его выполнения. Почему? Потому что в некоторых случаях при переходе в различное состояние, будут выполняться одни и те же действия. Например, при изменении положения управляющих колес для выполнения поворота направо и при изменении положения колес из позиции для левого поворота в нейтральную, необходимо повернуть их вправо на один и тот же градус. Поэтому неплохо было бы оптимизировать этот блок, включив в него только "уникальные" действия. Но тогда для того, чтобы передавать действие, необходимое для выполнения в этом блоке, необходимо для него тоже завести код, подобные тем, что заводились для кодирование событий.

Диаграмма переходов тоже измениться - в ней появятся обозначения для действий, выполняемых для управления тележкой:

Где,

• Event = 0 – показания на сенсоре меньше 14 см.
• Event = 1 – показания на сенсоре больше 14 см., но меньше 16 см.
• Event = 2 – показания на сенсоре больше 16 см.
• Action = 0 – положение управляющих колес не изменяется
• Action = 1 – повернуть управляющие колеса вправо
• Action = 2 – повернуть управляющие колеса влево

Для состояний тоже введен код, чтобы ими было проще манипулировать в программе. Может показаться, что состояния S0, S1 и S2 можно расшифровать как

• S0 – состояние движения прямо
• S1 – состояние выполнения поворота направо
• S1 – состояние выполнения поворота налево

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

Измененная диаграмма переходов, теперь может быть прочитана следующим образом:
Когда робот находится в состоянии S0, при наступлении события 0, робот переходит в состояние S1 и выполняет действие 1. Когда робот находится в состоянии S2, при наступлении события 0, робот переходит в состояние S1 и выполняет действие 3.

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

Прежде, чем писать программу, диаграмму переходов удбно в начале представить в виде следующих таблиц:

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

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

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

Например, двумерный массив States описывал бы как новое состояние зависит от пришедшего события и старого состояния, а двумерный массив Actions содержал бы в себе логику выбора действия для соответствующего события и состояния.
Тогда определение нужного действия и нового состояния выглядела бы следующим образом:

Action = Actions[Event][OldState]
NewState = States[Event][OldState]
Вывод: иногда, при поступлении одного и того же события, действия, выполняемые программой, должны быть разные, в зависимости от того, какие действия уже были выполнены (в каком состоянии программа находится) к текущему моменту работы программы, в каком . В таких случаях, схема работы программы должна учитывать предыдущее состояние программы для выбора "управляющего" действия и нового состояния. С другой стороны, действия при переходе из разных состояний могут быть одними и теми же, поэтому имеет смысл закодировать "уникальные" действия и использовать этот код в блоке определения действия. Расшифровка кода и выполнение действий, в таком случае, выносится в отдельный блок. Поскольку кодирование теперь используется как для событий, таки и для действий и состояний, то выбор действия и нового состояния выгодно описать двумя таблицами, которые позволяют существенно упростить логику программы, особенно, при возможности использовать массивы.