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

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

Лестница – наоборот, проверяет больше конструкторские навыки, программирование робота, там чисто номинальное.
Сортировщик – предъявляет высокие требования и к конструированию и программированию.

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

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



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

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

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

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


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

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




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

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


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


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

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