ДО курс по робототехнике

3 апреля 2013 г.

Робот для состязаний: сортировка кубиков - логистическая задача

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

Давайте взглянем еще раз на это задание.

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




Робот стартует из зеленой области. Корзины для кубиков обозначены цифрами 1, 2, 3, …, 8. Корзины отделены друг от друга перегородками в 5 см. высотой.

Если произвести простые расчеты, то получается:
2 мин. / 8 кубиков = 120 сек. / 8 кубиков = 15 сек. на один кубик.

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

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


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

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




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

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


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


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

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



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

Например:

Регламент Международной олимпиады описывает подготовку к состязанию "Сортировщик" следующим образом (перевод с сайта robosport.ru): 
Команды должны заявить, по каким признакам их робот будет рассортировывать предметы, и в какие из "Сортировочных корзин" поместит их.

В тоже самое время, текущие правила всероссийского этапа олимпиады говорят, что командам заранее не известно в какие карзины нужно будет разместить отсортированные кубики:
"1.2. В день соревнований, до времени сборки (тренировки), будет объявлено, какие кубики и в какие сортировочные области необходимо переместить. Это будет сделано размещением специальных сортировочных карточек в случайно выбранные сортировочные области."

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

Итак, представим себе, что робот нашел кубик на "свалке" и распознал его цвет и размер. Что дальше? Очевидно, что везти его в нужную корзину. А какая "нужная"? Дело в том, что хотя размер кубика и его цвет для человека бы однозначно ассоциировался с нужной корзиной, то робота нужно научить делать такую ассоциацию.

На самом деле этот вопрос можно разбить на два связанных между собой:
  1. Какая корзина нужна для текущего кубика?
  2. Где находится такая карзина?

На поле всего расположено 8 корзин, для простоты их все можно пронумеровать цифрами от 1 до 8.


Когда перед состязанием карточки будут разложены, то может оказаться, что:
  • Корзина 1 - для маленьких зеленых кубиков
  • Корзина 2 - для больших красных кубиков
  • Корзина 3 - не используется
  • Корзина 4 - для больших синих кубиков
  • Корзина 5 - не используется
  • Корзина 6 - для маленьких синих кубиков
  • Корзина 7 - для больших зеленых кубиков
  • Корзина 8 - для маленьких красных кубиков


Самый простой способ поставить соответствие соорудить ветвистое дерево из условий. И если на текстовых языках программирования оно еще будет смотреться более-менее компактно (хотя и там размашисто). То на графических языках NXT-G и Robolab - эта конструкция может занимать не один экран (особенно, вдобавок к самой программе распознования цвета и размера).
Например, так

или так (прчием это только один блок - аналогичные нужны для синего и зеленого цветов)

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

На самом деле есть возможность обойтись и без лазаний по множественным условиям. Для этого можно ввести двойное кодирование корзин.
Первый код будет отвечать на вопрос "Какая корзина нужна для текущего кубика":
КубикКод 1
Большой красный0
Маленький красный1
Большой зеленый2
Маленький зеленый3
Большой синий4
Маленький синий5

Второй код будет обозначать "Где находится такая корзина":
Код 1Место для корзины
02
18
24
36
47
51

Если внимательно присмотреться к первому коду, то можно заметить, что
  1. Большие кубики имеют четный код, маленькие нечетный
  2. Кубики сгруппированы по парам: красные начинаются с 0, зеленые с 2, синие с 4
Это позволяет код вычислять арифметической операцией: "номер цвета" * 2 + "код размера".

Важно понять, что этот первый код не поменяется, даже если корзины поменяются местами.

Поэтому теперь в программе вместо кодирования номера корзины будем применять "первый код":

или


Декодирование получившегося значения в нужный номер корзины, делается очень элегантно. Значение из переменной, используется как индекс в блоке Разветвления (Switch). А внутри каждой секии этого блока уже выставляет номер реальной корзины.

Его даже вынести в отдельную процедуру (My Block). И теперь, когда корзины на поле меняют свое расположение, вам нужно будет просто подправить этот простенький фрагмент программы, так чтобы секции блока Switch отображали нужные номера корзин.

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

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

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