Я пытаюсь создать карту препятствий в довольно грубом двухмерном пространстве сетки, используя разведку. Я обнаруживаю препятствия, пытаясь переместиться из одного пространства в смежное, и, если это не удается, в пространстве назначения возникает препятствие (в этой задаче нет понятия датчика дальности).
пример сетки http://www.eriding.net/resources/general/prim_frmwrks/images/asses/asses_y3_5d_3.gif (например)
Процесс завершен, когда все достижимые квадраты были посещены. Другими словами, некоторые пространства могут быть совершенно недоступны, даже если у них нет препятствий, потому что они окружены. Это ожидается.
В простейшем случае я мог бы использовать алгоритм DFS , но я боюсь, что это займет слишком много времени - робот потратит больше времени на возвращение, чем на исследование новой территории. Я ожидаю, что это будет особенно проблематично при попытке добраться до недоступных квадратов, потому что робот исчерпает все возможности.
В более изощренном методе правильной вещью, по-видимому, является разложение клеток Бустрофедона .
Однако я не могу найти хорошее описание алгоритма разложения ячеек Бустрофедона (то есть полное описание в простых терминах). Существуют такие ресурсы, как этот , или этот более общий, по вертикальной декомпозиции ячеек, но они не дают большого понимания ни алгоритмов высокого уровня, ни соответствующих структур данных низкого уровня.
Ответы:
Разложение клеток бустрофедона - это просто подразделение среды на области, которые могут быть эффективно покрыты путем бустрофедона. Трапецеидальная декомпозиция подойдет и может быть выполнена с использованием алгоритма линейной развертки. См. [Choset 2000], Этот веб-сайт или (я рекомендую!) Превосходную книгу «Вычислительная геометрия» Марка де Берга, et. al, для полного описания структур данных и алгоритмов требуется.
Выбрал, Хауи. «Покрытие известных пространств: клеточная декомпозиция Boustrophedon» Автономные роботы , 2000.
Например, рассмотрим множество препятствий как ребра и вершины. Допустим, среда также ограничена специальным многоугольником. У нас есть что-то вроде следующего. Чтобы разложить это пространство, мы просто добавляем вертикальные ребра между каждой вершиной и ближайшей линией или вершиной.
Чтобы выполнить это в коде, вам нужен только тест пересечения отрезка линии, отсортированный список ребер и отсортированный список вершин.
Когда это сделано, множество новых ребер и вершин охватывает только трапеции. Но я подчеркиваю, вы не можете сделать это онлайн (без предварительного знания препятствий). Если вы хотите сделать надежное покрытие без предварительного знания, вы можете посмотреть на «алгоритмы ошибок». В частности, вот простой алгоритм, предполагающий, что среда ограничена.
Из начальной позиции двигайтесь вверх и влево, пока не дойдете до верхнего левого угла окружения. Если вы столкнулись с препятствием первым, вы должны объехать его. Вы знаете, что что-то является препятствием, если его можно обойти (удар и движение).
Слева вверху двигайтесь вправо, пока не встретите границу. Затем двигайтесь вниз и влево (мы делаем биострофон всего пространства).
Когда вы находитесь на лево-правой линии и сталкиваетесь с препятствием, у вас есть два варианта. (i) Мы можем совершить кругосветное плавание, пока не достигнем лево-правой линии, которую мы пытаемся преодолеть, а затем продолжить. (ii), мы можем развернуться и покрыть новую лево-правую линию, пока не найдем наш путь через препятствие или не окажемся в этой ситуации снова. Я проиллюстрирую.
Слева мы движемся вокруг препятствия, пока не сможем вернуться к «линии», которой мы пытались следовать. Справа мы продолжаем покрывать (меньшую) область с одной стороны препятствия.
Преимущество первого метода заключается в том, что вы всегда полностью определяете препятствие перед тем, как принять решение о том, как его обойти, таким образом, вы можете выбрать более короткий путь. Преимущество второго метода заключается в том, что вам совсем не нужно обходить препятствие, вы можете просто перейти к тому месту, где находитесь.
Обратите внимание, что это определяет ваше разложение бустрофедона онлайн : вы покрываете область между препятствиями или между препятствиями и границей.
Однако, насколько я знаю, первый метод легче анализировать. Более сложные алгоритмы (например, BFS и т. Д.) Выбираются либо потому, что среда не ограничена (вы не хотите тратить вечно на поиски границ), либо существует очень неприятное препятствие на пути к разделению среды. Почему это плохо? посмотрите на этот пример:
Перемещение влево-вправо, а затем по кругу каждый препятствие создает путь слишком много крышек мелких деталей между каждым препятствием. Фактически, без глобального планирования пути вы можете сделать это настолько же плохим, как и разрешение вашей сетки, разместив эти столбцы шириной 1 пиксель, такой же высотой, как и вся среда, и на расстоянии 1 пикселя. Тогда вам придется передвигаться вокруг препятствия каждый раз, когда вы его преодолеваете.
Вот почему я спросил, есть ли у вас какое-то представление о том, где вы находитесь в окружающей среде, или вы можете заняться глобальным планированием пути. Но онлайн и оффлайн обсуждение и оптимальные алгоритмы для этого не то, что вы действительно хотели.
Обновление: мне пришлось удалить изображения (не https), и я опубликую это, что часто используется в реальных реальных приложениях. http://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/yamauchi_frontiers.pdf
источник
В итоге я обнаружил, что лучший способ сделать это - использовать очень простую концепцию: Flood Fill . Я использовал основанный на стеке итеративный подход вместо рекурсивного параметра и изменил его для физического пространства, используя поиск A *, чтобы найти путь от текущего местоположения до следующего местоположения в стеке (используя только те квадраты сетки, которые уже посетили, так как я гарантированно иметь путь между ними).
Эффективность кажется довольно разумной.
источник