Дискретная оптимизация активного местонахождения объекта

Например, если значение критерия является полным пройденным расстоянием, то он представляет собой аддитивный критерий, и веса ребер суммируются (то же самое для общего времени, проведенного в дороге). Если все критерии являются аддитивными, то соответствующий метод называется линейной сверткой: скалярный вес вычисляется как линейная комбинация компонент векторного веса. Формально, если W (γ) ∈ Rn - векторный вес, то скалярный вес вычисляется как:Однако, что, если стоит задача выбрать наименее опасный путь, а веса ребер - показатели опасностиотдельных составляющих пути, тогда вместо суммирования весов вам нужно выбрать самый большой, чтобы представить весь путь. Это называется критерием максимального типа. Если все критерии являются максимальными, соответствующая свертка выглядит так:Если применяетcя несоответствующий метод свертки, принцип оптимальности Беллмана, который используется алгоритмом Дейкстры, не будет выполнен, и результаты могут не иметь никакого смысла.Другая проблема заключается в том, что в зависимости от решаемой задачи могут быть оптимальные (даже оптимальные по Парето) решения, которые нельзя будет найти вне зависимости от того, как выбирались параметры λi.3. 3.Алгоритмы поиска кратчайшего путиДейкстры (Dijkstra’s algorithm)Несмотря на длительную историю и множество разработанных решений к настоящему времени в рамках новых задач не прекращается поиск новых алгоритмов, обеспечивающизее решение. Широкийдиапазон практических применений определяет высокий уровень ее значимости для многих приложений. Например поиск кратчайшего пути востребована в мобильной робототехнике для прокладки оптимального маршрута. Использование алгоритма Дейкстрыпоиска кратчайшего пути обеспечивает определение расстояние от одной вершины графа до существующих других. При этом нужнопомнить, что этот алгоритм можно применять только для графов, имеющихне отрицательные веса ребер. Каждая из вершин графа V при этом сопоставляется определенной метке, соответствующей минимальному известному расстояниюот определенной вершины до вершины а. Алгоритм является пошаговым, то есть с каждым шагом, он «проходит» одну вершину и уменьшает метку. Завершение алгоритм происходит, когда каждая вершина посещена. Если не все вершины посещены, то нужно выбрать такую вершину u, для которой метка является минимальной. В рамках этого алгоритма рассматриваются возможные пути, для которых вершина u оказывается предпоследнимпунктом маршрута. Вершина, в которую приходит ребро из u является ее соседом. Для каждой соседской вершины u, помимо посещенных, рассматривается новая длина пути, равная сумме текущего значения метки и расстоянию до ребра, которое соединяет u с соседской вершиной. В случае, когда длина меньше величины соседской метки, данная метка изменяет свое значение на полученную длину. После изучения всех соседских вершин u помечается как посещенная и алгоритм идет на следующий цикл[9]. Алгоритм Беллмана — Форда (Bellman–Ford algorithm)Этот алгоритм поиска кратчайшего пути дает возможность определить путь до вершин взвешенного графа. При этом ребра могут иметь отрицательный вес (это отличает его от алгоритмам Дейкстры). В этом алгоритме используются неориентированные или ориентированные графы (для примера G) со взвешеннымизначениями ребер. Длина пути равна сумме весов всех ребер, включённых в путь. Необходимо найти кратчайший путь из определенной точки s до каждой вершины графа.Псевдокод алгоритма Беллмана – Форда представляет собой следующий вид:𝑏𝑒𝑙𝑙𝑚𝑎𝑛𝑓𝑜𝑟𝑑 (𝐺,𝑤,𝑠) 𝑑[𝑠]=0 𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑣∈𝑉−{𝑠} 𝑑𝑜 𝑑[𝑣]= ∞ 𝑓𝑜𝑟 𝑖=1 𝑡𝑜 |𝑉|−1 𝑑𝑜 𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑒𝑑𝑔𝑒 (𝑢,𝑣)∈𝐸 𝑑𝑜 𝑖𝑓 𝑑[𝑣]>𝑑[𝑢]+𝑤(𝑢,𝑣) 𝑡ℎ𝑒𝑛 𝑑[𝑣]=𝑑[𝑢]+𝑤(𝑢,𝑣)Стоит указать, что кратчайшей путь может отсутствовать. Граф, имеющий отрицательный суммарный вес цикла, содержит бесконечно малый путь между вершинами цикла (при каждом обходе циклом уменьшается длина пути). Цикл, сумма весов рёбер которого отрицательна, называется отрицательным циклом [9]. Как уже было отмечено выше предыдущие работы в этой области включают расширения алгоритма Дейкстры, при этом одним из наиболее известных и имеющих широкие приложения стал алгоритм A*. Алгоритм поиска A* (Algorithm A star) Данный алгоритма поиска позволяет определить стоимость пути от начальной точки до целевой, используя первое наилучшее совпадение в графе. Обход вершин определяет эвристическая функция «длина пути + цена» (принято обозначать f(x)). Данная функция получается путем сложения двух функций: 1) Стоимость (цена) достижения вершины и начального положения (принято обозначать g(x) – может являться и эвристической, и нет). 2) Эвристическая оценка расстояния от заданной точки до конечной (принято обозначать h(x)). Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками. С использованием данного алгоритма все пути рассматриваются пошагово, и идут от заданной точки к целевой, до тех пор, пока не будет достигнута минимальная стоимость пути. В начале поиска, что характерно для всех информационных алгоритмов поиска, рассматриваются «кажущиеся» маршруты к целевой точки. Отличительной особенностью этого алгоритма от «жадного», является то, что данный алгоритм производит учет всего пройденного пути. Функция g(x), в свою очередь, является показателем стоимости маршрута от начальной позиции, а в «жадном» алгоритме данная функция отвечает только за стоимость пути от предыдущей вершины. При начале поиска рассматриваются вершины, граничащие с начальной точкой; выбирается вершина с минимальным значением f(x), и алгоритм переходит на этот узел. Во время каждой итерации алгоритмом рассматривается множество путей из начала графа до не посещённых вершин, которые размещаются в специальной очереди с разными приоритетами.Данный приоритет можно определить по выражению f(x) = g(x) + h(x). Итерации продолжаются до тех пор, пока функция f(x) конечной вершины графа не будет наименьшей из всех значений в очереди, либо, когда закончится просмотр графа. Итоговое решение выбирается из всех решений, у которых наименьшая стоимость. Алгоритм A* всегда может найти решение, при условии его существования, и относится к полным алгоритмам [13]. Алгоритм поиска D* (Algorithm D star) Алгоритм поиска кратчайшего пути во взвешенном ориентированном графе, где структура графа неизвестна заранее или постоянно подвергается изменению. Постановка задачи. Дан взвешенный ориентированный граф G(V, E). Даны вершины f и t. Требуется в процессе движения по кратчайшему пути в графе G обновлять значения функции g(s) при поступлении новой информации о графе G. На основе алгоритма А* описывается алгоритм D*, который способен определять расстояние между текущей вершиной f, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной t при каждом изменении графа в то время, как "робот" движется вдоль найденного пути [7]. 3.4. Модифицированнаязадача и алгоритм Дейкстры поиска кратчайших путей для векторно-весовой функцииРассмотрим направленную сеть (N, A), где N = {1, ..., n} - множество n узлов, A ⊂ N ⨯ N - множество дуг и связанный с каждой дугой (s, t )∈A - векторный весdst = (dstl, ..., dstm) ∈ Rm.Для случая m = 1 различные кратчайшие задачи с участием (N, А) изучались довольно широко. Стандартные результаты обобщены в работах Christofides [11], Deo [12], Hu [13], Johnson and Johnson [14] и Phillips и Garcia-Diaz [15]. Однако для общего m такие проблемы не анализировались. В настоящей работе рассматривается общий случай с использованием понятия минимизации Парето (или эффективности или минимизации вектора), определяемой следующим образом. Точка x* =(x1*, ..., xm*)∈X⊂Rmявляется минимумом Парето (или эффективным минимумом точки или вектора) X, если х* не снижается (является недоминируемой) снизу на X, т.е. если его не существуетх = (x1, ..., xm)∈Xдля которыхxi≤ xi*, i = 1, ..., m, xj < xj, для некоторых j∈{1, ..., m}.Обозначим х*∈vmin X.Здесь представлен алгоритм нахождения всех кратчайших путей Парето в (N, A) между узлами 1 и i, i = 1, ..., n, то есть для получениягде Pi - множество путей от узла 1 до узла i в (N, A), а суммирование в (1) является векторной суммой.Задача (I) сводится к стандартной задаче кратчайшего пути при m = 1. Предположим, что A не содержит петель, так как цикл либо не является частью кратчайшего пути Парето, либо является частью бесконечного номер. Также предполагается, чтоdst≠ (0, ..., 0), для (s, t) ∈A, чтобы избежать вырождения цепей. Никаких ограничений по знакам компонентов dst не производится. Алгоритм применяется к неориентированным графам поcредством замены каждой неориентированной дуги двумя направленными.В алгоритме 2.1 ниже для решения (I) метка Lki представляет собой множество длин всех путей Парето от узла 1 до узла i, содержащих k или меньшее количество дуг. В отличие от некоторых других процедур маркировки, никакие метки узлов не считаются окончательными до тех пор, пока не будут помечены все.Алгоритм 2.1 требует процедуры вычисления vmin на шаге 2. Такой метод представлен в Алгоритме 2.2.Шаг I. Положим di = (0, ..., 0), i = 1, ..., nи dij = (∞, ..., ∞), i ≠ j,Если нет дуги от i до j. Положим k = 1 иL1i = {d1i}, i = 1, ..., n.Шаг 2. Для i = 1, ..., n, положим где dji + Lkj = {dji + lkj: lkj∈Lkj}.Шаг 3. ЕслиLik+l =Lik.I = i, i = 1,. . . , n,stop; иначе перейти к шагу 4.Шаг 4. Если k = n - 1, останов. Отрицательная цепь существует. В противном случае присвоитьk = k + 1 и перейти к шагу 2.3.2.3. Алгоритм 2.2Шаг 1. Инициализовать i = 1, j = 2.Шаг 2. Если i= r-1, перейти к шагу 6. ​​Если vj≤ vi, перейти к шагу 3. Если vi≤ vj, перейти к шагу 4. Иначе перейти к шагу 5.Шаг 3. Присвоитьi = i + 1, j = i +1. Перейти к шагу 2.Шаг 4. Присвоить vj = vr, r = r-1. Перейти к шагу 2.Шаг 5. Если j = r, положитьvi∈vminV; перейти к шагу 3. Иначеприсвоитьj = j + l и перейти к шагу 2.Шаг 6. Если vj ≤ vi, положить vj∈vmin V.Останов. Если vi ≤ vj, положить vi∈vmin V.Останов. В противном случае присвоитьvi, vj∈vmin V.Останов.3. 5.Пример реализации алгоритма ДейкстрыРассмотрим пример реализации алгоритма Дейкстры. На рисунке 3 показан граф, в котором левая вершина - это начальная точка, самая правая - конечная точка.Окончательные отметки будут иметь темно-серый цвет, а «новые окончательные» отметки будут иметь красный цвет. Цвет знака совпадает с цветом ребра, ведущего к нему, а индекс является его «родительской» меткой.На нулевой итерации мы делаем начальную (0,0) метку и помечаем ее окончательной. На рисунке 3.2 показан результат первой итерации:Рисунок 3.2. Результат первой итерации поискаПодмножество Парето P = = {(1,2), (5,1)}, поэтому эти метки становятся окончательными. Вторая итерация показана на рисунке 3.3.Рисунок 3.3. Граф после второй итерацииНеобходимо обратить внимание, что метка (4,6) не используется, потому что этот путь хуже, чем (3,5) по обоим критериям. Подмножество Парето после второй итерации представляет собой P = {(3,5), (4,4), (7,3)}. Третья итерация показана на рисунке 3.4.Рисунок 3.4. Результат третьей итерацииМетка (7,3) не образует нового пути, поскольку он будет хуже по всем критериям, чем существующие. Подмножество Парето P = {(3,6)}. Четвертая итерация: показана на рисунке 3.5.Рисунок 3.5. Граф после четвертой итерацииМетка (3,6) также не образует нового пути. После этой итерации все метки являются окончательными. Итак, у нас есть 3 оптимальных решения Парето, показанные на рисунке 3.6Рисунок 3.6. Оптимальные решения ПаретоМодифицированный обобщенный алгоритм Дейкстры дает возможность найти все оптимальные пути по Парето. Вместо одной скалярной метки каждая вершина теперь имеет несколько векторных меток, каждая из которых является весом оптимального пути Парето к этой вершине. Некоторая часть меток вершин может быть окончательной, а другие нет.Чтобы иметь возможность «запоминать» оптимальные пути, для каждого знака (кроме начального) нужно сохранить ребро, ведущее к его вершине, и метку предыдущей вершины, используемой для ее вычисления.Маркеры становятся окончательными, если они находятся в подмножестве множества Парето, образованного из всех не конечных отметок и всех отметок конечной вершины. Все «новые окончательные» отметки используются как начальная точка для следующей итерации.3.6. Алгоритм А* поиска кратчайшего путиA* был разработан группой исследователей, работающих над планированием перемещения робота Shakey the Robot.В 1968 году исследователь в области ИИ Нильс Нильссон [19]пытался улучшить планирование маршрута движения Shakey the Robot, робота-прототипа, который мог перемещаться по комнате, содержащей препятствия. Этот алгоритм поиска пути, который Нильссон назвал A1, был более быстрой версией тогдашнего наиболее известного метода, алгоритма Дейкстры, предназначенного для поиска кратчайших путей в графах. Бертрам Рафаэль предложил некоторые существенные улучшения по этому алгоритму, назвав пересмотренную версию A2. Затем Питер Э. Харт ввел аргумент, в соответствии с которым A2 с минимальными изменениями является наилучшим алгоритмом для поиска кратчайших путей. Затем Харт, Нильссон и Рафаэль [22]совместно разработали доказательство того, что пересмотренный алгоритм А2, названный А*, поскольку он включал все предыдущие модификации, был оптимален для поиска кратчайших путей при определенных четко заданных условиях.На каждой итерации своего основного цикла A* необходимо определить, какой из его частичных путей должен расширяться на один или несколько более длинных путей. Это делается на основе оценки стоимости (общего веса), которая по-прежнему должна идти к целевому узлу. В частности, A * выбирает путь, который минимизируетf (n) = g (n) + h (n),где n - последний узел пути, g (n) - стоимость пути от стартового узла до n, а h(n) - эвристика, которая оценивает стоимость пути с наименьшей стоимостью от n до цели. Эвристика является специфической для задачи поиска А*. Для алгоритма поиска фактического кратчайшего пути эвристическая функция должна быть допустимой, что означает, что она никогда не переоценивает фактическую стоимость, чтобы добраться до ближайшего узла цели.Типичные реализации A* используют очередь приоритетов для выполнения повторного выбора минимальных (оцененных) узлов затрат для расширения. Эта очередь приоритетов известна как открытый набор или (очереди с приоритетомopen). На каждом шаге алгоритма узел с самым низким значением f(x) удаляется из очереди, соответственно обновляются значения f и g его соседей, и эти соседи добавляются в очередь. Алгоритм продолжается до тех пор, пока целевой узел не будет иметь более низкое значение f, чем любой узел в очереди (или пока очередь не будет пуста). Значение цели f равно длине кратчайшего пути, так как h в цели равен нулю в допустимой эвристике.Если эвристика h удовлетворяет дополнительному условию h (x) ≤ d (x, y) + h (y) для каждого ребра (x, y) графа (где d обозначает длину этого ребра), то h называется монотонным или последовательным. В таком случае A* может быть реализован более эффективно - грубо говоря, ни один узел не должен обрабатываться более одного раза (закрытое множество closed), а A* эквивалентно выполнению алгоритма Дейкстры с уменьшенной стоимостью d '(x, y) = d (x, y) + h (y) - h (x).Предполагается, что эвристическая функция является монотонной (или последовательной), что часто встречается во многих практических задачах, таких как поиск кратчайшего пути в дорожных сетях. Однако, если предположение неверно, узлы в закрытом множестве могут быть открыты заново и их стоимость может улучшиться. Другими словами, закрытое множество можно опустить (тогда он сводится к алгоритму поиска дерева), если гарантируется существование решения, или если алгоритм адаптирован таким образом, что новые узлы добавляются в открытый набор только в том случае, если они имеют более низкое значение f, чем на любой предыдущей итерации.ЗаключениеПоиск объектов, представляющих интерес, становится необходимым условием для многих роботизированных задач, таких как мобильные манипуляции. В работе изученазадача активного визуального поиска в больших, неизвестных или частично известных средах. Используя неопределенную семантику среды, робот, которому поручено находить объект, может разработать эффективные стратегии поиска, которые могут находить заданные объекты в масштабе всего здания, которое ранее неизвестно роботу. Выполненная работа также обеспечивает инструмент решения оптимизации многокритериальных задач оптимизации маршрутов поиска и описывает различные алгоритмы решения таких задач. Подобные задачи часто решаются путем свертки нескольких критериев к единой целевой функции или переформулировкой многокритериальной задачи как задачи с несколькими ограничениями одной целевой функцией.Такие подходы являются, как правило, спорными и неоднозначными.Если задача имеет более одной цели, то они формируют множество Парето.Наиболее распространенным алгоритмом для вычисления всех паретооптимальных путей является обобщение алгоритма Дейкстры (Парето-Дейкстра). В ходе выполнения работы была достигнута поставленная цель и решены частные задачи. При этом были получены следующие результаты:проведен анализобзор литературных источников по методам визуального поиска;планирование маршрута происходит в дискретизованном пространстве конфигурации манипулятора робота;изучены особенности постановки и методы решения многокритериальных оптимизационных задач;реализован алгоритм Дейкстры оптимального построения маршрута поиска как многокритериальной задачи для получения Парето-оптимального решения.Список использованной литературыISO Standard 8373:1994, Manipulating Industrial Robots – Vocabulary. A.PronobisandP.Jensfelt,“Large-scalesemanticmappingandreasoning with heterogeneous modalities,” in Proc. IEEE Int. Conf. Robot. Autom., May 2012, pp. 3515–3522J.P. Merlet, Parallel Robots, 2nd ed., Springer, Dordrecht, (2006). T.W. Lee, D.C.H. Yang, “On the Evaluation of Manipulator Workspace”, ASME Journal of Mechanisms, Transmissions, and Automation in Design, 105: 70-77, (1982). S. Dibakar, T.S. Mruthyunjaya, “A computational geometry approach for determination of boundary of workspaces of planar manipulators with arbitrary topology”, Mechanism and Machine Theory 34: 149-169, (1999). Dudek G., Jenkin M. Computational principles of mobile robotics. – 2nd rev. ed. – Cambrigde Univ. Press, 2010. – 406 p. Фирсов М.А., Ивановский С.А. Параллельная реализация алгоритма построения пересечения простых полигонов с использованием технологии CUDA // Известия СПБГЭТУ «ЛЭТИ». – 2013. – № 9. – С. 29–34. Guibas L.J., Motwani R., Raghavan P. The robot localization problem // The SIAM J. on Computing. – 1997. – № 26. – P. 1120–1138. Скворцов А.В. Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции // Вычисл. методы и программирование. – 2002. – Т. 3. – С. 116–123. De Berg M., Cheong O., Van Kreveld M., Overmars M. Computational geometry: algorithms and applications. – 3nd rev. ed. – Berlin; Heidelberg: Springer-Verlag, 2008. – 386 p. Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. М., 1978.Ху Т. Целочисленное программирование и потоки в сетях, М.: Мир, 1974. - 520 с.JOHNSON, D. E., and JOHNSON, J. E., Graph Theory with Engineering Applications, Ronald Press, New York, New York, 1972.Филлипс Д.,Гарсия-Диас А. Методы анализа сетей: пер. с англ. М. Мир, 1984. — 496 с. ФордЛ.Р., Фалкерсон Д.Р. Потоки в сетях. : пер. с англ.– М.: Мир, 1966, 356с.Moore, E. F., The Shortest Path through a Maze, Proceedings of the International Symposium on the Theory of Switching, Part II, pp. 285-292, 1957; Annals of the Computation Laboratory of Harvard University, Harvard University Press, Cambridge, Massachusetts, Vol. 30, 1959.Bellman, R. E., On a Routing Problem, Quarterly of Applied Mathematics, Vol. 16, pp. 87-90, 1958.Эвристический поиск [Электронный ресурс]. – Режим доступа: http://chernykh.net/content/view/293/493/. Дата обращения: 13.03.2017 г. Hart, P. A Formal Basis for the Heuristic Determination of Minimum Cost Paths / P. Hart, N. Nilsson, B. Raphael // IEEE Trans. Syst. Science and Cybernetics. – 1968. - № SSC-4(2). – C. 100-107. Koenig, S. Incremental Heuristic Search in Artificial Intelligence / S. Koenig, M. Likhachev, Y. Liu, D. Furcy // Artificial Intelligence Magazine. – 2004. - № 25(2). - C. 99-112. Cormen, Thomas H. Introduction to Algorithms Third Edition Thomas / Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. – Ldn. : The MIT Press, 2009. – 1313 c. Deo, N. Shortest-path algorithms: Taxonomy and Annotation / N. Deo, C. Pang // Networks. – 1984. - № 14. - С. 275–323. Алгоритм Дейкстры. Электронный ресурс. Режим доступа: https://ru.wikipedia.org/wiki/Алгоритм_ДейкстрыАлгоритм Беллмана-Форда. Электронный ресурс. Режим доступа: https://ru.wikipedia.org/wiki/Белмана_ФордаАлгоритм А*. Электронный ресурс. Режим доступа: https://ru.wikipedia.org/wiki/Алгоритм_поиска_А*Алгоритм D*. Электронный ресурс. Режим доступа: http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_D*