Найти местоположение, используя только расстояние и направление?

Question

Триангуляция работает путем проверки вашего угла до трех ИЗВЕСТНЫХ целей.

"Я знаю, что это Александрийский маяк, он расположен здесь (X, Y) на карте, и это справа от меня на 90 градусов". Повторите еще 2 раза для разных целей и углов.

Трилатерация работает путем проверки вашего расстояния от трех ИЗВЕСТНЫХ целей.

«Я знаю, что это Александрийский маяк, он расположен здесь (X, Y) на карте, и я в 100 метрах от него». Повторите еще 2 раза для различных целей и диапазонов.

Но оба эти метода основаны на знании ЧТО вы смотрите.

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

У вас есть робот, медленно движущийся по этому лесу.

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

1) Если это существует, как оно называется? Я ничего не могу найти.

2) Как вы думаете, шансы иметь два одинаковых местоположения «хиты»? Я думаю, это довольно редко.

3) Если есть два идентичных местоположения «хиты», как я могу определить свое точное местоположение после того, как переместлю робота дальше. (Я предполагаю, что шансы иметь 2 появления ТОЧНЫХ углов подряд после того, как я переставлю робота, были бы статистически невозможны, за исключением леса, растущего рядами как кукуруза). Буду ли я просто снова вычислять позицию и надеяться на лучшее? Или я бы каким-то образом включил мою предыдущую оценку позиции в мое следующее предположение?

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

Answer 1

Отличный вопрос.

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

2. Идентификация наземных ориентиров - одна из скрытых «уловок», лежащих в основе робототехники. Если невозможно однозначно идентифицировать ориентир, вы можете получить большую долю дезинформации, особенно учитывая, что реальные датчики являются стохастическими (то есть / с результатом будет некоторая неопределенность). Выбор подходящего метода локализации почти наверняка будет зависеть от того, насколько хорошо вы сможете однозначно определить ориентир или связать шаблоны ориентиров с картой.

3. Самым простым методом самокализации во многих случаях является локализация Монте-Карло . Одним из распространенных способов реализации этого является использование фильтров частиц. Преимущество этого состоит в том, что они хорошо справляются, когда у вас нет великолепных моделей движения, сенсорных возможностей и вам нужно что-то надежное, что может справиться с неожиданными эффектами (такими как перемещение препятствий или затенение ориентиров). Частица представляет одно возможное состояние транспортного средства. Первоначально частицы равномерно распределены, поскольку транспортное средство движется и добавляет больше наблюдений датчика включены. Состояния частиц обновляются для удаления от неожиданных состояний - в данном примере частицы будут удаляться из областей, где диапазон / подшипники не соответствуют тому, что должно быть видно из текущей оценки положения. При достаточном времени и наблюдениях частицы имеют тенденцию слипаться в области, где существует высокая вероятность обнаружения транспортного средства. Посмотрите работы Себастьяна Труна, особенно книгу "Вероятностная робототехника".

Answer 2

То, что вы ищете, - это локализация по методу Монте-Карло (также известная как фильтр частиц). Вот хороший ресурс по теме .

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

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

Answer 3

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

Затем вы можете идентифицировать ориентиры, перебирая деревья и вычисляя расстояние до всех его соседей. В Matlab вы можете использовать pdist, чтобы получить список всех (уникальных) парных расстояний.

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

Как только вы найдете все ориентиры, вы просто триангулируете.

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

Answer 4

• (1) «Роботизированное картирование» и «алиасинг восприятия».
• (2) Два идентичных попадания неизбежны . Поскольку робот может различать только конечное число X из различимых древовидных конфигураций, даже если конфигурации совершенно случайные, почти наверняка есть хотя бы одно местоположение, которое выглядит "таким же", как какое-то другое местоположение, даже если вы встречаете далеко меньше, чем X / 2 разных деревьев. Это так называемые "столкновения парадоксов дня рождения". Возможно, вам повезет, что конкретное местоположение , в котором вы находитесь, на самом деле уникально, но я бы не стал ставить на него своего робота.

Итак, вы:

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

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

Один из подходов - прикрепить (не обязательно уникальную) «подпись» к каждому дереву, которая описывает его положение относительно ближайших деревьев.

Затем, когда вы путешествуете, робот подъезжает к дереву и находит «подпись» для этого дерева, и вы находите все деревья на карте, которые «соответствуют» этой подписи. Если на карте соответствует только одно уникальное дерево, то дерево, которое ищет робот , может быть тем деревом на карте (да, вы знаете, где находится робот) - поместите весомую, но условную точку на карта в относительном положении робота к соответствующему дереву - дереву, рядом с которым стоит робот, определенно не является ни одним из других деревьев на карте. Если несколько деревьев на карте совпадают - все они имеют одинаковую неуникальную подпись - тогда вы могли бы поместить несколько менее весомых предварительных точек на карту в позиции роботов относительно каждого из них. Увы, даже если найдено одно или несколько совпадений, все же возможно, что дерево, на которое смотрит робот, вообще не находится на карте, и сигнатура этого дерева совпадает с одним или несколькими деревьями на карте, и таким образом, робот может быть в любом месте на карте. Если ни одно из деревьев на карте не совпадает, то дерево, на которое смотрит робот, определенно отсутствует на карте. (Возможно, позже, когда робот точно знает, где он находится, он должен начать , добавив эти деревья на карту?)

Направляясь по дорожке, вы нажимаете точки в предполагаемом направлении и скорости движения.

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

Самая простая подпись - это список расстояний от конкретного дерева до ближайших деревьев. Определенное дерево на карте «сопоставляется» с конкретным деревом в лесу, когда для каждого и каждого близлежащего дерева на карте имеется соответствующее близлежащее дерево в лесу на «одинаковом» расстоянии, насколько это возможно. расскажите с вашим известным расстоянием и угловыми ошибками.

(Под «рядом» я имею в виду «достаточно близко, чтобы робот мог быть в состоянии точно подтвердить, что дерево действительно существует»), хотя, вероятно, проще сопоставить это с чем-то вроде «Мой робот» я могу видеть все деревья в диапазоне R, так что я собираюсь потрудиться даже , пытаясь сопоставить деревья, которые находятся в пределах круга R * 1/3 от моего робота, и мой список расстояний включайте только деревья, которые находятся в окружности R * 2/3 от конкретного дерева, которому я пытаюсь соответствовать ").

Если вы знаете свою ориентацию север-юг даже приблизительно, вы можете создавать сигнатуры, которые являются «более уникальными», то есть имеют меньше поддельных совпадений на карте и (мы надеемся) в реальном лесу. «Соответствие» для дерева, рядом с которым стоит робот, происходит, когда для каждого ближайшего дерева на карте есть соответствующее дерево в лесу на «одинаковом» расстоянии и направлении, насколько вы можете судить по известному расстоянию. и угловые ошибки. Скажем, вы видите, что у дерева «Фред» на карте есть другое дерево в 10 метрах в квадранте от N до W, но робот находится рядом с деревом, которое определенно не имеет деревьев на таком расстоянии в квадранте от N до W , но у него есть дерево в 10 метрах к югу. В этом случае (используя более сложную подпись) вы определенно можете сказать, что робот не находится рядом с Фредом, даже если простая подпись даст (ложное) совпадение.

Другой подход: «Цифровая бумага» решает аналогичную проблему ... Можете ли вы посадить несколько деревьев по схеме, специально разработанной для легкого распознавания?

Answer 5

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