Решение задачи о ханойских башнях с помощью конструктора Lego Mindstorms NXT 2.0

Шахматов Александр Александрович

Студент

ФГБОУ ВПО «Шадринский государственный педагогический институт»

ЗАДАЧА О ХАНОЙСКИХ БАШНЯХ

Эту известную логическую головоломку придумал французский математик Эдуард Люка, в 1883 году [2]. Суть заключается в следующем: даны три стержня, на один из которых нанизаны восемь блинов, причем блины отличаются размером и лежат меньший на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть больший блин на меньший.

Рис. 1. Модель Ханойской башни с восемью дисками

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

Для решения данной задачи была сконструирована мобильная роботизированная установка (МРУ), изображенный на рис. 2.

Рис. 2. МРУ для решения «Ханойских башен»

Основной частью данного робота является манипулятор, который может двигаться вертикально, за счет двигателя и цепи, и горизонтально, за счет своего колесного основания. Т. к. в основе манипулятора лежит сервомотор, конструкция получается с большой массой, которой требуется противовес, в качестве которого смог быть использован блок управления NXT. В целом, конструкция похожа на двухчелюстной грейферный экскаватор (нем. Greifer, от greifen — xватать), применяющийся для захвата сыпучих материалов, скрапа и стружки, крупнокусковых каменных и волокнистых материалов, а также длинномерных лесоматериалов [1], с одним отличием — для регулирования положения цепи нужно использовать рычаг на лебедке, т. к. с помощью деталей Lego NXT 2.0 невозможно создать конструкцию полностью аналогичную использующимся на данный момент конструкциям в реальных экскаваторах.

Рис. 3. Грейферный экскаватор

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

Рис. 4. Одинарная главная передача с двумя коническими зубчатыми колесами.

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

Из-за недостаточно большой (большая высота требовала гораздо большего противовеса, чем мы могли себе позволить) высоты лебедки, а так же из-за больших размеров грейфера было принято решение поставить МРУ на подставку.

Для уменьшения количества регуляторов, а соответственно и удешевления конструкции при реальном производстве, было принято решение не использовать датчики, идущие в комплекте Lego NXT 2.0. На практике было достаточно той точности, которую позволяли достичь регуляторы, встроенные в сервоприводы (текущий угол наклона мотора от изначального, количество градусов, на которое повернулся мотор от начала работы программы и пр.). Но у данной схемы есть один существенный недостаток: полностью теряется возможность коррекции МРУ в ходе работы программы и большая чувствительность к начальным условиям, то есть необходима точно заданная начальная позиция и точно позиционированная, имеющаяся в наличии, деревянная головоломка.

Таким образом, у нас имеется следующая схема работы МРУ:

1. На начальном этапе имеется МРУ, находящаяся в необходимом состоянии — грейфер (в) находится в наивысшем положении, челюсти грейфера раскрыты, позиционирование грейфера осуществляется по первому стержню, откуда будет взят первый блин. МРУ располагается строго параллельно физической модели головоломки.

2. Лебедка с рычагом (б) опускает грейфер (в) до заранее вычисленного уровня, на котором челюсти грейфера будут захватывать ровно один блин.

3. Сервопривод грейфера (в) должен воздействовать с помощью прямой передачи на его челюсти, которые плотно захватывают ровно один блин.

4. Лебедка с рычагом (б) поднимает грейфер (в) с зафиксированным блином до наивысшего состояния.

5. Шасси (а) передвигает МРУ параллельно физической модели до необходимого стержня, на который будет опущен зафиксированный блин (расстояние между стержнями заранее известно).

6. Лебедка с рычагом (б) опускает грейфер до уровня, на котором блин надевается на стержень.

7. Сервопривод грейфера (в) раскрывает челюсти, зафиксированный блин оказывается на необходимом стержне.

8. Лебедка с рычагом (б) поднимает грейфер до наивысшего уровня.

9. Шасси (а) передвигает МРУ до следующего стержня, откуда будет снят следующий блин.

10. Переход к пункту 1.

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

Листинг программы на языке NXC представлен в приложениях.

Список использованных источников

1. Балашов В.П. Грузоподъёмные и транспортирующие машины на заводах строительных материалов / В. П. Балашов — М.: Машиностроение — 1987 — 384с., ил.

2. Гарднер М. Математические головоломки и развлечения / М. Гарднер. 2-е изд., испр. и доп. — Пер. с англ.— М.: Мир, 1999 — 447с.