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

В предыдущих двух заметках (1, 2), было рассмотрено два аспекта решения задания для старшей группы из Международной робототехнической олимпиады. Первый аспект – определение стратегии по сколько кубиков робот будет захватывать и как он их будет перемещать. Второй аспект затрагивал некоторые особенности программирования робота для этого задания – как заранее предусмотреть возможность того, что корзины для сортировки могут располагаться в различных местах.

В этой заметке предлагается рассмотреть еще один аспект – как запрограммировать перемещение между свалкой и корзинами.

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

Сначала рассмотрим первый случай - перемещение только одного кубика за раз.

В прошлый раз обсуждалось две возможности перемещения по одному кубику:

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

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

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

   Движение робота при этом методе можно описать следующим образом:

   

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

   • из опорной точки в корзину 1
   • из опорной точки в корзину 2
   • . . .
   • из опорной точнки в корзину 7
   • из опорной точнки в корзину 8
   • из опорной точки к левой свалке
   • из опорной точнки к правой свалке
   • путь от корзин с левой стороны к финишу
   • путь от корзин с правой стороны к финишу
   

   Каждый такой маршрут удобно представить в виде отдельной процедуры (My Block).

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

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

   

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

   2. Перемещение проходит сразу вдоль корзин (как вариант вдоль боковых черных линии).
      
      

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

      Описать работу робота, функционирующего по данной схеме, можно следующим образом:

      
      

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

      
      
   3. И самый сложный, прямолинейный.
      
      

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

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

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

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

   Раньше он был простым – если количество обработанных кубиков стало меньше 5, то свалка должна "рабочая" свалка теперь будет другая.

   
   

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

   
   

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

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



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