se.moevm.info

1. Робот-пылесос
Исходная постановка задачи:
Построить траекторию (и пройти по ней), которая покрывает всю территорию карты (пропылесосит весь пол).
Исходные данные:
Робот начинает движение около “базы” в неизвестном мире. Строит карту мира и определяет своё местоположение (знает всегда координаты базы относительно себя). Робот знает габариты своего чистящего устройства, исходя из этого должен построить траекторию очистки всей территории.
Ограничения на исходные данные:

• Окружающий мир - такая замкнутая область, из каждой точки которого видно базу (выпуклая область).
• У робота есть лазерный дальномер (нет одометрии).

Усложнения:

• Нет базы (но появляется одометрия), мир может быть произвольным.
  

2. Искатель сокровищ
Исходная постановка задачи:
Разведать подземелье, найти золото.
Исходные данные:
Робот ищет золото в подземелье. Робот не знает карту подземелья, должен также определять, в какой части подземелья он находится. Необходимо обойти всё подземелье (также предоставить траекторию перемещения) и найти спрятанные сокровища.
Ограничения на исходные данные:

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

Усложнения:

• В подземельях могут присутствовать ловушки, которые также необходимо распознать и объехать.

3. Футбол
Исходная постановка задачи:
Симулировать игру двух команд роботов с целью закатить мяч в чужие ворота
Исходные данные:
Две команды, один мяч. Можно давать пас, можно вести мяч. Наезжать друг на друга нельзя. Можно отобрать мяч (как во время паса, так и у едущего с ним робота). Игра до победного гола (нескольких голов)
Ограничения на исходные данные:

• В команде три-пять роботов, один из которых вратарь. Разрешено использование коллективного разума для принятия решения или наличие одного централизованного мозга.
• У роботов есть координаты других относительно друг друга, а также координаты мяча.

Усложнения:

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

4. Битва роботов
Исходная постановка задачи:
Две армии роботов бьются друг с другом.
Исходные данные:
Есть несколько типов роботов, (быстрый, сильный, далеко стреляющий) которые должны расположится на карте и одолеть команду противника. Они подчиняются командиру, который раздаёт приказы, решает, когда робота нужно перебросить на другой фланг и прочее. Необходимо уничтожить вражеского командира.
Ограничения на исходные данные:

• У роботов есть полоска здоровья.
• Роботам известна карта.
• Командир знает координаты каждого из своих роботов.
• Роботы могут видеть вражеских юнитов, но изначально не знают их координат.

Усложнения:

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

5. Робот-матка
Исходная постановка задачи:
Обеспечить жизнеобеспечение матке колонии роботов.
Исходные данные:
Есть единственная матка-робот. Для её жизнеобеспечения необходимо пропитание. В колонии присутствуют роботы-рабочие, которые могут быть отправлены в разведку или для добычи пищи из уже известного источника пропитания.
Ограничения на исходные данные:

• Роботов рабочих большое, но ограниченное число. Им пища не нужна.
• Матка - единый мозг, отдающий приказы.
• Карта неизвестна, её отображение, которое построили роботы-разведчики хранится у матки, но не у других роботов.
• Матка даёт исчерпывающие команды, например: “принести пищу из этой точки, куда следует добраться так-то.” Или: “Отправится в эту точку и снять развед-данные”.

Усложнения:

• Роботы могут пропадать (их может кто-то съедать), причём матка не может узнать, что кого-то съели, она лишь может узнать о невыполненном задании по истечении времени.
• Роботы не могут наезжать друг на друга.

6.Автопилот
Исходная постановка задачи:
Спланировать маршрут с учётом прочих участников движения.
Исходные данные:
Есть множество участников движения, о траекториях движения которых всё известно. Есть пропускная способность дороги: количество рядов, длина. На дорогах есть перекрёстки со светофорами. Необходимо проложить маршрут от заданной точки до заданной, принимая во внимания все траектории прочих участников движения, не вызывая заторов и коллизий.
Ограничения на исходные данные:

• Проложенный маршрут уже не корректируется. Под него подстраиваются новые участники
• Новые участники могут стартовать в любой момент времени, не обязательно все сразу.
• Карта известна, все маршруты известны, время старта новых участников движения неизвестно.
• На светофорах все стартуют одновременно и мгновенно набирают наибольшую скорость. Торможение происходит аналогично.
• Можно использовать единый мозг-диспетчер, однако также можно строить маршрут на собственном узле.

Усложнения:

• Светофоры имеют разное (заданное) время.
• На дороге может появиться машина с приоритетом (скорая, пожарная, полиция…) О её появлении мгновенно узнают все участники движения. Её маршрут известен, все перестраиваются так, чтобы машина с приоритетом проехала с наиболее высокой скоростью.

7.Коррекция прицела
Исходная постановка задачи:
Установить прицел на цели, вести цель, поразить цель.
Исходные данные:
Оперативник с снайперской винтовкой уничтожает цели на поле боя. Цели появляются хаотически. Задача поразить как можно больше целей за время работы программы.
Ограничения на исходные данные:

• Цели передвигаются в трёхмерном мире из стороны в сторону (слева направо, справа налево, снизу вверх, по диагонали и прочее). До каждой из целей есть своё расстояние. Пуля летит с какой-то скоростью и ей потребуется время, на преодоление этого расстояния. Стрелять необходимо с упреждением.
• Цели движутся равномерно прямолинейно.
• Открывать огонь можно только при получении соответствующей команды от человека-оператора. Если команды нет какое-то время, переключиться на другую цель.
• На стрельбище присутствуют препятствия, попадание в которых не приводит к поражению цели.

Усложнения:

• На стрельбище присутствует ветер (направленный в плоскости движения целей), ветер в произвольное время меняет своё направление. Оперативник знает, куда дует ветер сейчас, но не знает, куда он будет дуть следующий момент времени. Как следствие, он может промазать.
• У пули есть погрешность. Она летит не в ту точку, куда был произведён выстрел. Во-первых, пуля летит по угасающей траектории. Во-вторых, её направление может на малую ошибку отличаться от изначально заданного направления.
• Цели могут двигаться неравномерно (может менять ускорение, скорость пересчитывается), но стрелок в каждый момент времени знает, точное значение ускорения тела и может построить оценку положения цели.

8.Корпус Нова
Исходная постановка задачи: Предотвратить таранный удар флагманом Ронана планеты Ксандара. Исходные данные: Корабли корпуса Нова - маленькие патрульные летательные аппараты, не имеющие оружия. Однако выстроившись в матрицу они способны создать непреодолимый щит. Задача выстроить щит, пока флагман Ронана не уничтожил Ксандар. Ограничения на исходные данные: Флагман Ронана с какой-то заданной скоростью сбивает произвольные корабли корпуса Нова, которые не включились в матрицу. Матрица - прямоугольная сетка кораблей корпуса Нова. Корабли корпуса Нова подлетают к формирующейся матрице, но подключаются к ней только тогда, когда полностью сформирован ряд или столбец. Корабли, встроившиеся в матрицу, неуничтожимы флагманом Ронана. Кораблей корпуса Нова неограниченное число, но у них одна единственная точка вылета. Цель считается достигнутой, если матрица нужно размера построена и расположена на безопасном (заданном) расстоянии от планеты до того, как это расстояние достигнет флагман Ронана. Усложнения: Матрицу можно формировать на расстоянии от флагмана, но если матрица будет находится в непосредственной близости, это снизит скорость движения флагмана пропорционально количеству кораблей в матрице. Флагман Ронана в приоритете сбивает корабли корпуса Нова, которые подлетели к матрице, но ещё пока не включились в неё. Матрица может формироваться из нескольких эпицентров. Очистить поле битвы Исходная постановка задачи: Очистить местность с неизвестной картой от следов боя. Исходные данные: Турнир многих рас, проводимый Xaero, завершён. В турнире приняли участие как представители людей, так и роботов, а также инопланетян. Нужно убрать следы крови и тела, имея в распоряжении роботов-чистильщиков. Ограничения на исходные данные: Кровь разных существ очищается разными чистильщиками. Причём мёртвые тела должны быть перенесены в специальное место специальными роботами. Карта неизвестна, чистильщикам даётся команда перемещения человеком-оператором. Карта может состоять из разных уровней, переход между уровнями может осуществляться с помощью лифтов, телепортов, лестниц. Усложнения: На карте может остаться недобитый участник турнира. У оператора есть несколько охранных роботов. Следы этого побоища также должны быть ликвидированы. Необходимо успеть до начала следующего турнира.

Добыча волков Исходная постановка задачи: Найти и загнать цель стаей волков. Исходные данные: Стая волков охотится в лесу на неизвестной карте. Задача найти добычу, устроить на неё охоту, окружить. Ограничения на исходные данные: Местность лесистая, следовательно окружение состоит из окружностей. Волки не умеют ходить сквозь деревья Жертва стремиться избежать стаи, однако начинает бежать только когда заметит стаю (есть радиус видимости, меньший, чем у волков). Задача волков окружить цель, для этого они могут использовать разные тактики: оставить группу волков в засаде, остальными загонять; бежать полукругом и прочее. Жертва бежит с той же скоростью, что и волки. Однако, если волк укусит жертву, её скорость уменьшится. Усложнения: Жертва убегает зигзагами. Причём, если она набегает головой на волка, то не получает повреждений, но отбрасывает волка. Жертв может быть в лесу несколько, возможно переключение с жертвы на жертву. Жертвы бегают с разной скоростью. У волков накапливается усталость - они не могут долго бежать.

Спаси этих котят. Исходная постановка задачи: Во время наводнения перенести всех котят с опасного места на безопасное. Исходные данные: Идёт большая вода. Маме-кошке необходимо перенести своих котят с затопляемой территории. Мама-кошка знает местность и знает, где будет вода через некоторое время. Однако она не знает когда вода будет в каком месте. Ограничения на исходные данные: Вода занимает участки мгновенно. Через воду кошка переправляться не может. Изначально котята на месте, которую затопит вода (в последнюю очередь). Кошке задано место, куда надо отнести котят. Если кошка двигается по маршруту, но оказывается, что этот маршрут уже преграждает вода, кошка должна спланировать и изменить свой текущий маршрут, а также последующие маршруты перемещения. Усложнения: Котята медленно разбредаются из точек эвакуации (но не заходят в воду). Их надо отлавливать и возвращать. Кошке неизвестна местность. Она узнаёт её по ходу движения.

Рой неистребим. Исходная постановка задачи: Зерги должны удержать позиции под атакой протоссов. Исходные данные: Зерги подверглись массированной атаке тамплиеров протоссов. Задача удержать позиции до тех пор, пока королева Керриган не уничтожит тамплиеров. Ограничения на исходные данные: Зерги имеют только маленьких беспомощных зерлингов, которые не могут оказать сопротивление организованной атаке тамплиеров. Они лишь могут создавать живой щит. Тамплиеры атакуют флангом, высаживая войска в любой точке фланга Тамплиеры протоссов уничтожают зерлингов как только подходят к ним. Тамплиеров уничтожает королева Керриган как только подходит к ним. Зерлингов неограниченное число, но подкрепление может не дойти к моменту, когда один из аванпостов окажется захвачен протоссами. Тамплиеров протоссов ограниченное число. Усложнения: Тамплиеры могут появляться в любой точке карты (в тылу). Тамплиеры наносят урон Керриган, которая медленно регенерирует. Сара Керриган должна выжить.

Ненавижу некромантов. Исходная постановка задачи: Убежать от зомби. Исходные данные: На неизвестной карте присутствуют некроманты. Сами по себе они не опасны. Но раз в какое-то время они воскрешают рядом с собой зомби. Задача найти выход из помещения и не быть съеденным зомби. Ограничения на исходные данные: Чем дольше вы блуждаете по помещению, тем больше зомби восстанут за вами охотится. Вы двигаетесь быстрее, чем зомби, но понятия не имеете, где эти зомби располагаются. На карте вы можете найти артефакты различных свойств (замедляют призыв зомби у некромантов, убивают всех зомби на карте, дают временную неуязвимость к укусам и прочее). Зомби не знают где выход и просто бесцельно блуждают по карте, пока не обнаружат вас. Усложнения: Людей, пытающихся выбраться несколько, и вы, если вам не удалось сбежать и вы были укушены, становитесь охотником на выживших. Задача становится поймать их всех. (upd к предыдущему усложнению) Выходов открывается несколько, как только ты превращаетесь в зомби.

Пронести кольцо. Исходная постановка задачи: Избегая Всевидящего Ока Саурона, необходимо пронести кольцо всевластия и выбросить его в Ородруин. Исходные данные: На неизвестной карте с кучей препятствий, которую периодически осматривает Всевидящее Око, необходимо пересечь Мордор и дойти до Ородруина. Ограничения на исходные данные: Око имеет радиус обзора. В нём нельзя оставаться дольше какого-то фиксированного времени. У вас есть запас сил. Он не бесконечен. Карта Мордора плоская, но имеет непреодолимые препятствия, которые необходимо обойти. Из-за препятствий всевидящее Око имеет слепые зоны. Око располагается высоко (по оси OZ), следовательно может видеть поверх любого препятствия. Усложнения: На карте присутствует Голлум, мечтающий отнять у вас свою прелесть. Вы успешно от него отбиваетесь (телепортируя его в произвольную точку карты) но это отнимает у вас выносливость. Око Саурона осматривает карту произвольно (в произвольный момент времени может смениться ускорение осмотра, скорость поворота сектора обзора соответственно пересчитывается).

Гензель и Гретель. Исходная постановка задачи: Найти выход на неизвестной карте. Карту запоминать нельзя. Исходные данные: На неизвестной карте необходимо найти выход. Строить и запоминать карту нельзя. За собой остаётся след из хлебных крошек. Ограничения на исходные данные: У вас есть скан местности, по которому можно определить, в какую сторону можно двигаться. Один раз в некоторый интервал времени за вами остаётся хлебная крошка, символизирующая, что в этом участке карты вы уже были. Карту запоминать нельзя. Выход определяется сразу, как только он оказывается в радиусе видимости скана. Усложнения: Крошки исчезают с течением времени.

Разобрать статью. Статья посвящённая amcl (adaptive Monte-Carlo localization). http://papers.nips.cc/paper/1998-kld-sampling-adaptive-particle-filters.pdf Разобрать принцип работы скан-матчера. Реализовать. Протестировать на тестовом окружении. Статья посвящённая base_local_planner. www.cs.washington.edu/ai/Mobile_Robotics/postscripts/colli-ieee.ps.gz http://cs.stanford.edu/group/manips/publications/pdfs/Brock_1999_ICRA.pdf Разобрать принцип планировщика. Реализовать. Протестировать на тестовом окружении. 3) Статья посвящённая Fast SLAM

  http://robots.stanford.edu/papers/Montemerlo03a.pdf
  Разобрать суть статьи. Выявить правило определения фич. Протестировать для разных сканов.