Я пытаюсь реализовать алгоритм под названием «быстро исследующее дерево случайных убеждений». Цель этого алгоритма — придумать путь для робота, который вместо того, чтобы связать начало и цель с метрикой наименьшего расстояния или чем-то подобным, ведет робота в области, где он может получить измерения с высокой точностью, и только затем перемещается к цели.
При реализации алгоритма я начинаю с построения графа путем случайной выборки заданного пространства. Каждый раз, когда выбирается новая точка, к графику добавляется новое ребро. Первоначально ошибка в положении робота будет высокой, так как он не будет получать хорошие измерения, но как только дерево, через которое я исследую, достигает «хорошей» области, ошибка робота внезапно падает, и с этим знанием где находится «хорошая» область, я просматриваю граф назад, обрезая ранее соединенные ребра и соединяя эти вершины с хорошей областью. Учитывая достаточное количество выборок, в оптимальном сценарии граф будет распространяться наружу от хорошей области, поэтому соединение любых двух вершин гарантирует, что вы пройдете через эти точки.
Вот где у меня проблема. Как только я начинаю обход, чтобы обрезать и обновить свои ребра, алгоритм не должен обрезать ребра, которые соединяют хорошую область с начальной точкой, что приведет к бесконечному циклу. Пример показан на этой картинке:
Алгоритм находит вершины 1, 2, 3 и 4. Связи 1 -> 2, 2 -> 3, 2 -> 4.
Теперь мы находим № 5, который является «хорошей» областью для робота. Посещение этой вершины волшебным образом повысит ее точность в будущем. Нахожу соседние вершины из 5: нахожу №3. Я обновляю родителя № 3 до № 5 вместо № 2. Теперь, если бы вокруг #3 было больше вершин, я бы прошёл и их и обновил их родителей до #3 и т.д., таким образом создав путь от #5 ко всем этим. (Для получения дополнительной информации, обход по существу вычисляет ковариацию робота, если бы он переместился из № 5 в № 3, и является ли это более желательным, чем переход из № 2 в № 3).
- Но ни при каких обстоятельствах я не должен обновлять родителя № 2 до № 3: потому что единственный способ, которым робот попал в № 5, был через № 2.
Чтобы избежать этого, я сделал простую (но крайне неэффективную?) вещь: вычислил кратчайший путь к вершине, из которой я начал свой обход, и если какая-либо вершина, с которой я столкнулся во время обхода, является частью этого пути, я не обновить своего родителя. Это работает достаточно хорошо за счет больших вычислительных затрат, потому что мне нужно делать это каждый раз, когда мне нужно вернуться назад с обновлением, поэтому мне было интересно, есть ли лучший и эффективный способ сделать это.
