четверг, 10 марта 2011 г.

Робот для состязаний: сортировщик - между корзиной и свалкой. Часть II

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

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

Да, конечно, можно поиграться с расположением опорной точки, и это даже может принести положительные результаты для какого-нибудь «удобного» расположения кубиков и сортировочных областей. Но просто ожидать такой удачи, довольно безрассудно, поэтому логично выглядит попытка придумать какой-нибудь универсальный алгоритм.

Например, что если ехать сразу к интересующей робота корзине, минуя опорную точку.

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

"Ага!", воскликнут те, кто дружит с математикой – "у нас 8 потенциально возможных мест куда нужно будет вести первый кубик, и 8 мест куда нужно везти второй кубик. Т.е. из каждой корзины, нужно проложить 8 различных маршрутов, и таких корзин - 8. Итого, это 8x8=64 различных комбинаций корзин, 64 различных маршрута!"

Да, но нужно посмотреть что из себя представляют эти маршруты.
  1. Перемещаемся в соседнюю правую корзину
    1-2, 2-3, 3-4, 5-6, 6-7, 7-8
  2. Перемещаемся в соседнюю левую корзину
    2-1, 3-2, 4-3, 6-5, 7-6, 8-7
  3. Перемещаемся в право через одну
    3-1, 4-2, 5-7, 6-8
  4. Перемещаемся влево через одну
    1-3, 2-4, 7-5, 8-6
  5. Перемещаемся вправо из крайней корзины в крайнюю
    5-8, 4-1
  6. Перемещаемся влево из крайней корзины в крайнюю
    1-4, 8-5
  7. Перемещаемся в противоположную корзину
    1-5, 5-1, 2-6, 6-2, 3-7, 7-3, 4-8, 8-4
  8. Перемещаемся со сдвигом на одну корзину вправо
    2-5, 5-2, 3-6, 6-3, 4-7, 7-4
  9. Перемещаемся со сдвигом на одну корзину влево
    1-6, 6-1, 2-7, 7-2, 3-8, 8-3
  10. Перемещаемся со сдвигом на две корзины вправо
    3-5, 5-3, 4-6, 6-4
  11. Перемещаемся со сдвигом на две корзины влево
    1-7, 7-1, 2-8, 8-2
  12. Перемещаемся из крайней левой корзины в крайнюю правую на противоположной стороне
    4-5, 5-4
  13. Перемещаемся из крайней правой корзины в крайнюю левую на противоположной стороне
    1-8, 8-1
Проверим, все ли переходы покрыты:

Где, "Z" – роботу никуда двигаться не надо – просто положить следующий кубик в ту же самую корзину.

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

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

Самый простой способ реализовать эту матрицу на NXT-G, если закодировать каждую ячейку матрицы числом:

Т.е. для описания такого массива в программе нам нужен будет блок Switch с 64-мя вкладками.

Также необходимо будет релизовать 13 подпрограмм (MyBlock) ответственных за то или иное перемещение.

Как только все 13 подпрограмм готовы, их нужно будет разместить аккуратно в нужных вкладках. Например, Блок "А" во второй, одиннадцатой, двадцатой и т.д., а блок "M" в восьмой и пятьдесят седьмой вкладках.

Тогда к этим подпрограммам можно обратиться с помощью следующего кода:


Продолжение следует...

2 комментария:

  1. сложно сориентироваться с первого раза
    почему вы пишете на nxt-g, давно доказано что в robolab*e робот обрабатывает программу в разы быстрее?

    ОтветитьУдалить
  2. А где в этой программе места, которые требуют высокой производительности?
    1. На сколько я знаю, для Robolab нужна своя прошивка.
    2. В ней не поддерживаются Lego Color сенсор
    3. NXT-G программы позволяют больше заниматься реализацией алгоритма, вместо реализации конкретной функциональности.

    ОтветитьУдалить

Related Posts Plugin for WordPress, Blogger...