воскресенье, 6 февраля 2011 г.

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

Продолжение. Начало здесь

Давайте рассмотрим алгоритм движения вдоль стены, предложенный в Задаче #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 плавных и движение прямо:


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

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

Комментариев нет:

Отправить комментарий

Related Posts Plugin for WordPress, Blogger...