Робомобили без водителей развозят пиццу. Такси без водителей развозят людей. Фуры без водителей развозят многотонные грузы. Если разобрать все эти эффектные проекты, мы придем к разным типовым задачам, важной из которых является поиск и оптимизация маршрутов. Такие задачи решаются с помощью теории графов. Тема эта непростая, изучается, в основном, уже в университете или, как минимум, в старших профильных классах. Но в этом посте я покажу, как с помощью LEGO EV3 освоить теорию графов уже в средней школе. Причем без зубрежки, а на увлекательном, прикладном уровне.
Автомобильный конвейер на основе EV3 от Danny’s LAB. Реально собирает LEGO-машинки. Но речь немного не о нем.
Чтобы беспилотный транспорт сам доехал куда надо, он должен уметь строить маршрут между заданными точками. Желательно кратчайший и согласующийся с правилами движения. Для моделирования и решения такой задачи нам потребуется мобильная платформа LEGO EV3 и, собственно, карта, по которой эта платформа будет двигаться.
Наша мобильная платформа должна быть оснащена датчиками и сервоприводами. Все необходимое можно найти в базовом образовательном наборе LEGO Mindstorms EV3 45544. Вот как примерно выглядит платформа:
Сборка не требует знаний электроники и занимает не более получаса. Платформа имеет все необходимое, чтобы подняться на высокий уровень абстракции в решении задачи.
Изобразим карту дорог в виде сетки. Линии — это дороги, точки пересечения — это перекрестки дорог:
Все отрезки дороги между перекрестками имеют одинаковую длину, движение на них двухстороннее. Некоторые дороги перекрыты — они помечены «кирпичом». Кроме того, все повороты на нашей карте кратны 90 градусам. Усложнение сетки дорог не повлияет на принцип решения задачи, и для наглядности мы обойдемся довольно простым вариантом. Наша задача — проехать из точки А в точку В про кратчайшему пути.
У каждого перекрестка есть свои координаты — номера линий по горизонтали и вертикали. В теории графов такие перекрестки называются вершинами. Дороги между перекрестками обозначены стрелками. В теории графов это ребра. Все дороги двусторонние (стрелки в обе стороны) значит граф неориентированный. Стоимость (время проезда) для всех участков дорог одинаковая, значит граф невзвешенный.
Граф, представленный картинкой, наглядно демонстрирует карту и связи внутри нее. Но на компьютере — в том числе на EV3 — обрабатывать графическую информацию трудоемко. Оптимальней закодировать граф матрицей, матрицей смежности.
Если между перекрестками нет прямого сообщения, в точке их пересечения мы ставим 0. Если есть — 1. Мы договорились, что все расстояния между соседними перекрестками у нас равны 1. Если бы граф был взвешенный, то вместо единицы в каждом пересечении мы бы проставили «вес» участка. А если бы учитывали направление движения, то матрица выше была бы несимметричной — в одну сторону могло быть 1, а в другую 0.
С матрицей смежности наш робот уже может решить задачу — найти кратчайший путь от А до B. Но матрица у нас двухмерная, а в EV3 можно хранить только одномерные массивы. Мы можем легко перейти к одномерному массиву через сдвиг n*Y+X, где n — размер матрицы.
Для решения будет использоваться алгоритм Дейкстры — алгоритм поиска кратчайшего пути между одной вершиной графа и всеми остальными. Алгоритм был изобретен в 1956 году голландским ученым Эдсгером Дейкстрой. Если объяснять максимально просто, то в основе алгоритма — последовательное продвижение к соседним вершинам графа при постоянной оценке пройденного пути. Хороший иллюстративный пример и базовую блок-схему алгоритма можно найти в статье на Википедии.
В нашем случае блок-схема алгоритма Дейкстры (наша «дейкстра») будет выглядеть следующим образом:
По алгоритму, а лучше по его математической модели мы уже можем создать программу для робота. Входными данными будет матрица смежности, стартовая и конечная точки. После всех описанных действий поиск кратчайшего пути между любыми точками на одной и той же карте можно будет находить быстро.
Разумеется, помимо алгоритма Дейкстры, нашему роботу на основе LEGO EV3 понадобится ряд более простых программных модулей (подпрограмм): движение по линии до перекрестка, подсчет перекрестков, повороты в оба направления, определение своего местоположения относительно абсолютной системы координат X,Y, Θ, где X,Y — координаты на сетке, Θ — текущее направление робота (выраженное через код, например 1 — вверх, 2 — направо, 3 — вниз, 4 — налево).
А вот живая демонстрация решения задачи. Входные данные несколько отличаются, но сути это не меняет.
В задачи по перемещению на местности можно интегрировать возможности одометрии — например, чтобы робот в лабиринте понимал, где он находится и куда движется. С помощью одометрии перемещение робота оценивается, исходя из данных о движении приводов (вращении двигателей). Зная диаметр колес, мы можем вычислить расстояние, которое проехал робот за определенное время. Зная угловые скорости колес, можем определить угол, на который робот повернулся относительно первоначального. А установив разные угловые скорости, можем настроить движение робота по дуге и при этом определять «петли» при передвижении робота, как на видео ниже:
В школах много внимания уделяется тригонометрии, но ее практическое применение никак не освещается. Задачи одометрии, решаемые с помощью LEGO EV3, показывают, зачем вообще может понадобиться тригонометрия. На практике одометрия используется не только в транспорте, но и, например, для отслеживания положения инструмента в станках с ЧПУ (числовым программным управлением).
Позволю себе немного рекламы. Задачу, описанную выше, и более сложные задачи вполне могут решать ребята 7-9 классов, которые прошли подготовку в клубах робототехники. Я веду один такой клуб, «Робит», в Екатеринбурге — вот наша программа обучения. Видео с демо к задаче выше мы снимали на одном из занятий. Тогда одна восьмиклассница из нашего клуба за 6 часов изучила основы теории графов и решила аналогичную задачу.
Решение задач невозможно без выбора подходящей среды программирования для LEGO EV3. О новинках в этой области есть отдельный материал. Я стараюсь научить ребят выбирать язык программирования под задачу, а не задачу под тот язык программирования, синтаксис которого они изучили. Но в младших классах сложно сразу работать в текстовом языке программирования, поэтому мы начинаем изучать алгоритмы в графических языках, где порог вхождения ниже. С 10 лет ученики осваивают графическую среду EV3 Mindstorms. Некоторые соревнования по робототехнике ограничивают инструментарий только этой средой.
С 12 лет ребята начинают осваивать среду EV3 Basic. Среда сравнительно проста в освоении, и Basic предлагает для платформы LEGO EV3 мощную функциональность. Помимо этого, мы программируем в среде EV3Dev, куда можно установить много разных языков — Python, Java, C. С помощью EV3Dev ребята получают первый опыт в трендовых, востребованных языках. Единственный минус EV3Dev — это сравнительно более низкая скорость опроса датчиков по сравнению с другими средами. При правильном подходе LEGO EV3 становится отличным инструментом для знакомства с программированием. Когда ученики видят, как их код вдыхает жизнь в конструктор, это превосходная мотивация.
Изучив подобные алгоритмы еще в средней школе, ребята смогут в дальнейшем закреплять свои знания и, например, участвовать в проектных и предметных олимпиадах, которые дают реальные бонусы — например, 100 баллов автоматом по ЕГЭ при поступлении в вузы.
Автомобильный конвейер на основе EV3 от Danny’s LAB. Реально собирает LEGO-машинки. Но речь немного не о нем.
Чтобы беспилотный транспорт сам доехал куда надо, он должен уметь строить маршрут между заданными точками. Желательно кратчайший и согласующийся с правилами движения. Для моделирования и решения такой задачи нам потребуется мобильная платформа LEGO EV3 и, собственно, карта, по которой эта платформа будет двигаться.
Мобильная платформа LEGO EV3
Наша мобильная платформа должна быть оснащена датчиками и сервоприводами. Все необходимое можно найти в базовом образовательном наборе LEGO Mindstorms EV3 45544. Вот как примерно выглядит платформа:
Сборка не требует знаний электроники и занимает не более получаса. Платформа имеет все необходимое, чтобы подняться на высокий уровень абстракции в решении задачи.
Карта дорог
Изобразим карту дорог в виде сетки. Линии — это дороги, точки пересечения — это перекрестки дорог:
Все отрезки дороги между перекрестками имеют одинаковую длину, движение на них двухстороннее. Некоторые дороги перекрыты — они помечены «кирпичом». Кроме того, все повороты на нашей карте кратны 90 градусам. Усложнение сетки дорог не повлияет на принцип решения задачи, и для наглядности мы обойдемся довольно простым вариантом. Наша задача — проехать из точки А в точку В про кратчайшему пути.
Граф
У каждого перекрестка есть свои координаты — номера линий по горизонтали и вертикали. В теории графов такие перекрестки называются вершинами. Дороги между перекрестками обозначены стрелками. В теории графов это ребра. Все дороги двусторонние (стрелки в обе стороны) значит граф неориентированный. Стоимость (время проезда) для всех участков дорог одинаковая, значит граф невзвешенный.
Матрица смежности
Граф, представленный картинкой, наглядно демонстрирует карту и связи внутри нее. Но на компьютере — в том числе на EV3 — обрабатывать графическую информацию трудоемко. Оптимальней закодировать граф матрицей, матрицей смежности.
Если между перекрестками нет прямого сообщения, в точке их пересечения мы ставим 0. Если есть — 1. Мы договорились, что все расстояния между соседними перекрестками у нас равны 1. Если бы граф был взвешенный, то вместо единицы в каждом пересечении мы бы проставили «вес» участка. А если бы учитывали направление движения, то матрица выше была бы несимметричной — в одну сторону могло быть 1, а в другую 0.
С матрицей смежности наш робот уже может решить задачу — найти кратчайший путь от А до B. Но матрица у нас двухмерная, а в EV3 можно хранить только одномерные массивы. Мы можем легко перейти к одномерному массиву через сдвиг n*Y+X, где n — размер матрицы.
Алгоритм Дейкстры
Для решения будет использоваться алгоритм Дейкстры — алгоритм поиска кратчайшего пути между одной вершиной графа и всеми остальными. Алгоритм был изобретен в 1956 году голландским ученым Эдсгером Дейкстрой. Если объяснять максимально просто, то в основе алгоритма — последовательное продвижение к соседним вершинам графа при постоянной оценке пройденного пути. Хороший иллюстративный пример и базовую блок-схему алгоритма можно найти в статье на Википедии.
В нашем случае блок-схема алгоритма Дейкстры (наша «дейкстра») будет выглядеть следующим образом:
По алгоритму, а лучше по его математической модели мы уже можем создать программу для робота. Входными данными будет матрица смежности, стартовая и конечная точки. После всех описанных действий поиск кратчайшего пути между любыми точками на одной и той же карте можно будет находить быстро.
Разумеется, помимо алгоритма Дейкстры, нашему роботу на основе LEGO EV3 понадобится ряд более простых программных модулей (подпрограмм): движение по линии до перекрестка, подсчет перекрестков, повороты в оба направления, определение своего местоположения относительно абсолютной системы координат X,Y, Θ, где X,Y — координаты на сетке, Θ — текущее направление робота (выраженное через код, например 1 — вверх, 2 — направо, 3 — вниз, 4 — налево).
А вот живая демонстрация решения задачи. Входные данные несколько отличаются, но сути это не меняет.
Бонусная тема: одометрия
В задачи по перемещению на местности можно интегрировать возможности одометрии — например, чтобы робот в лабиринте понимал, где он находится и куда движется. С помощью одометрии перемещение робота оценивается, исходя из данных о движении приводов (вращении двигателей). Зная диаметр колес, мы можем вычислить расстояние, которое проехал робот за определенное время. Зная угловые скорости колес, можем определить угол, на который робот повернулся относительно первоначального. А установив разные угловые скорости, можем настроить движение робота по дуге и при этом определять «петли» при передвижении робота, как на видео ниже:
В школах много внимания уделяется тригонометрии, но ее практическое применение никак не освещается. Задачи одометрии, решаемые с помощью LEGO EV3, показывают, зачем вообще может понадобиться тригонометрия. На практике одометрия используется не только в транспорте, но и, например, для отслеживания положения инструмента в станках с ЧПУ (числовым программным управлением).
Где можно всему этому научиться
Позволю себе немного рекламы. Задачу, описанную выше, и более сложные задачи вполне могут решать ребята 7-9 классов, которые прошли подготовку в клубах робототехники. Я веду один такой клуб, «Робит», в Екатеринбурге — вот наша программа обучения. Видео с демо к задаче выше мы снимали на одном из занятий. Тогда одна восьмиклассница из нашего клуба за 6 часов изучила основы теории графов и решила аналогичную задачу.
Как выбрать среду программирования LEGO EV3
Решение задач невозможно без выбора подходящей среды программирования для LEGO EV3. О новинках в этой области есть отдельный материал. Я стараюсь научить ребят выбирать язык программирования под задачу, а не задачу под тот язык программирования, синтаксис которого они изучили. Но в младших классах сложно сразу работать в текстовом языке программирования, поэтому мы начинаем изучать алгоритмы в графических языках, где порог вхождения ниже. С 10 лет ученики осваивают графическую среду EV3 Mindstorms. Некоторые соревнования по робототехнике ограничивают инструментарий только этой средой.
С 12 лет ребята начинают осваивать среду EV3 Basic. Среда сравнительно проста в освоении, и Basic предлагает для платформы LEGO EV3 мощную функциональность. Помимо этого, мы программируем в среде EV3Dev, куда можно установить много разных языков — Python, Java, C. С помощью EV3Dev ребята получают первый опыт в трендовых, востребованных языках. Единственный минус EV3Dev — это сравнительно более низкая скорость опроса датчиков по сравнению с другими средами. При правильном подходе LEGO EV3 становится отличным инструментом для знакомства с программированием. Когда ученики видят, как их код вдыхает жизнь в конструктор, это превосходная мотивация.
А что дальше?
Изучив подобные алгоритмы еще в средней школе, ребята смогут в дальнейшем закреплять свои знания и, например, участвовать в проектных и предметных олимпиадах, которые дают реальные бонусы — например, 100 баллов автоматом по ЕГЭ при поступлении в вузы.
