| dbo:abstract
|
- Der D*-Algorithmus ist ein Suchalgorithmus. Es handelt sich um eine Erweiterung des A*-Algorithmus und somit einen direkten „Nachfahren“ des Dijkstra-Algorithmus. Sowohl A* als auch der Dijkstra-Algorithmus sind in ihrer Grundform unflexibel und können auf Veränderungen im Graphen während oder nach der Expansion nicht reagieren. In beiden Fällen kann der Anwender alle Ergebnisse verwerfen und nochmal von vorne beginnen. Gerade bei Arbeiten mit Robotern oder Agenten unter realen Bedingungen (begrenzte Sensorreichweite, unbekannte Umgebung) kommt es vor, dass große Karten ständig aktualisiert werden.Anthony Stentz entwickelte an der Carnegie Mellon University eine Möglichkeit, A* so zu modifizieren, dass er mit den neuen Anforderungen funktioniert. (de)
- D* (pronounced "D star") is any one of the following three related incremental search algorithms:
* The original D*, by Anthony Stentz, is an informed incremental search algorithm.
* Focused D* is an informed incremental heuristic search algorithm by Anthony Stentz that combines ideas of A* and the original D*. Focused D* resulted from a further development of the original D*.
* D* Lite is an incremental heuristic search algorithm by Sven Koenig and Maxim Likhachev that builds on LPA*, an incremental heuristic search algorithm that combines ideas of A* and Dynamic SWSF-FP. All three search algorithms solve the same assumption-based path planning problems, including planning with the freespace assumption, where a robot has to navigate to given goal coordinates in unknown terrain. It makes assumptions about the unknown part of the terrain (for example: that it contains no obstacles) and finds a shortest path from its current coordinates to the goal coordinates under these assumptions. The robot then follows the path. When it observes new map information (such as previously unknown obstacles), it adds the information to its map and, if necessary, replans a new shortest path from its current coordinates to the given goal coordinates. It repeats the process until it reaches the goal coordinates or determines that the goal coordinates cannot be reached. When traversing unknown terrain, new obstacles may be discovered frequently, so this replanning needs to be fast. Incremental (heuristic) search algorithms speed up searches for sequences of similar search problems by using experience with the previous problems to speed up the search for the current one. Assuming the goal coordinates do not change, all three search algorithms are more efficient than repeated A* searches. D* and its variants have been widely used for mobile robot and autonomous vehicle navigation. Current systems are typically based on D* Lite rather than the original D* or Focused D*. In fact, even Stentz's lab uses D* Lite rather than D* in some implementations. Such navigation systems include a prototype system tested on the Mars rovers Opportunity and Spirit and the navigation system of the winning entry in the DARPA Urban Challenge, both developed at Carnegie Mellon University. The original D* was introduced by Anthony Stentz in 1994. The name D* comes from the term "Dynamic A*", because the algorithm behaves like A* except that the arc costs can change as the algorithm runs. (en)
- D* (pronunciado "D estrella") es uno de los siguientes tres algoritmos de búsqueda incremental:
* El D* original, por Anthony Stentz, es un algoritmo de búsqueda incremental informada.
* D* Enfocado es un algoritmo heurístico de búsqueda incremental informada creado por Anthony Stentz que combina ideas de A* y el D* original. D* Enfocado es el resultado de un desarrollo adicional de D* original.
* D* Lite es un algoritmo heurístico de búsqueda incremental creado por Sven Koenig y Maxim Likhachev que se basa en LPA*, combina ideas de A* y Dynamic SWSF-FP. Los tres algoritmos de búsqueda resuelven los mismos problemas de planificación de ruta basada en la suposición, incluyendo la planificación con la suposición de espacio libre, donde un robot tiene que navegar hasta las coordenadas de un objetivo dado en un terreno desconocido. Hace suposiciones sobre la parte desconocida del terreno (por ejemplo: que no contiene obstáculos) y encuentra un camino más corto desde sus coordenadas actuales hasta la meta bajo estas suposiciones. El robot entonces sigue el camino. Cuando se observa nueva información del mapa (como obstáculos previamente desconocidos), se añade la información a su mapa y, si es necesario, planea el nuevo camino más corto a partir de sus coordenadas actuales a las coordenadas del objetivo determinado. Se repite el proceso hasta que llega a las coordenadas del objetivo o determina que no se puede llegar a las coordenadas del objetivo. Al atravesar terrenos desconocidos, nuevos obstáculos se pueden descubrir con frecuencia, por lo que esta nueva planificación tiene que ser rápida. Los algorítmos de búsqueda (heurística) incremental aceleran las búsquedas de secuencias de problemas de búsqueda similares mediante el uso de la experiencia con los problemas anteriores para acelerar la búsqueda de la actual. Suponiendo que las coordenadas del objetivo no cambian, los tres algoritmos de búsqueda son más eficientes que las reiteradas búsquedas A*. D* y sus variantes han sido ampliamente utilizados para robots móviles y navegación de vehículos autónomos. Los sistemas actuales se basan normalmente en D* Lite en lugar del D* original o D* Enfocado. De hecho, incluso el laboratorio de Stentz utiliza D* Lite en lugar de D* en algunas implementaciones. Tales sistemas de navegación incluyen un sistema prototipo probado en Marte en los astromóviles Opportunity y Spirit y en el sistema de navegación de la obra ganadora en el DARPA Urban Challenge, todos desarrollados en la Carnegie Mellon University. El D* original fue presentado por Anthony Stentz en 1994. El nombre de D* viene del término "Dynamic A*", ya que el algoritmo se comporta como A* excepto que los costos de los arcos pueden cambiar a medida que se ejecuta el algoritmo. (es)
- L'algorithme D* (qui se prononce D étoile ou D star à l'anglaise) recouvre un ensemble de trois algorithmes de recherche incrémentale heuristique suivants :
* L'algorithme original D* (original D*), de Anthony Stentz, est un algorithme de recherche incrémentale informé.
* L'algorithme Focused D* (ou D* focalisé) est un algoritme de recherche incrémentale informé heuristique de Anthony Stentz qui combine des idées de A* et de l'algorithme original D*. L'algorithme D* focalisé résulte d'un développement plus poussé de l'algorithme D* d'origine.
* L'algorithme D* Lite (ou D* léger) est un algorithme de recherche incremental heuristique de et Maxim Likhachev qui s'appuie sur , un algorithme de recherche incrementale heuristique qui combine les idées de A* et Dynamic SWSF-FP. Les trois algorithmes résolvent les mêmes problèmes de planification de chemins à base d'hypothèses,incluant la planification avec l'hypothèse d'espace libre, dans laquelle un robot doit naviguer aux coordonnées d'un but donné en terrain inconnu. Il doit faire des hypothèses sur la partie inconnue du terrain (par exemple: qu'il ne contient pas d'obstacles) et trouver un chemin le plus court depuis ses coordonnées courantes vers les coordonnées du but selon ces hypothèses. Le robot suit alors le chemin. Lorsqu'il observe une nouvelle information cartographique (telle que des obstacles précédemment inconnus), il ajoute l'information à sa carte et, si nécessaire, replanifie un nouveau chemin le plus court depuis ses coordonnées courantes vers les coordonnées du but donné. Il répète le processus jusqu'à ce qu'il atteigne les coordonnées du but ou qu'il détermine que les coordonnées du but n'ont pas été atteintes. En traversant un terrain inconnu, de nouveaux obstacles peuvent fréquemment être découverts, donc cette replanification doit être rapide. Les algorithmes de recherche incrémentale heuristique accélèrent la recherche pour des séquences de problèmes de recherche similaires en utilisant l'expérience acquise sur des problèmes précédents pour résoudre plus rapidement le problème courant. Sous l'hypothèse que les coordonnées du but ne changent pas, tous les trois algoritmes de recherche sont plus efficients que des recherches A* répétées. D* et ses variantes ont été largement utilisés pour la navigation de robots mobiles et de véhicules autonomes. Les systèmes actuels sont typiquement basés sur D* Lite plutôt que sur le D* original ou Focused D*. En fait, même le laboratoire de Stentz utilise D* Lite plutôt que D* dans certaines implémentations. De tels systèmes de navigation incluent un système prototype testé sur les rovers de Mars Opportunity et Spirit et le système de navigation qui a remporté le , tous deux développés à l'Université Carnegie Mellon. L'algorithme D* original a été présenté par Anthony Stentz en 1994. Le nom D* vient du terme "Dynamic A*", parce que l'algorithme se comporte comme A* sauf que le coût des arcs change au fur et à mesure que l'algorithme s'exécute. (fr)
- Алгоритм поиска D* (произносится как «Ди стар») — это любой из трёх связанных :
* Оригинальный алгоритм D* Энтони Стенца — это информированный алгоритм инкрементного поиска.
* Сфокусированный D* — это алгоритм инкрементного эвристического поиска, разработанный Энтони Стенцем, который сочетает в себе идеи A* и оригинального D*. Сфокусированный D* возник в результате дальнейшего развития оригинального D*.
* Облегчённый D* — это алгоритм инкрементального эвристического поиска, созданный Свеном Кёнигом и Максимом Лихачёвым, который основан на LPA*, алгоритме инкрементального эвристического поиска, объединяющем идеи алгоритма поиска A* и динамического SWSF-FP. Все три алгоритма поиска решают одни и те же основанные на предположениях проблемы, включая планирование с предположением о свободном пространстве, когда робот должен перемещаться к заданным координатам цели на неизвестной местности. Он делает предположения о неизвестной части местности (например, что на ней нет препятствий) и находит кратчайший путь от её текущих координат до координат цели при этих предположениях. Затем робот следует по пути. Когда он наблюдает новую информацию на карте (например, ранее неизвестные препятствия), он добавляет эту информацию на свою карту и, при необходимости, перепланировывает новый кратчайший путь от текущих координат к заданным координатам цели. Он повторяет процесс до тех пор, пока не достигнет координат цели или не определит, что координаты цели не могут быть достигнуты. При пересечении неизвестной местности могут часто обнаруживаться новые препятствия, поэтому это перепланирование должно быть быстрым. Инкрементальные (эвристические) алгоритмы поиска ускоряют поиск последовательностей похожих поисковых задач, используя опыт решения предыдущих проблем для ускорения поиска текущей. Если предположить, что координаты цели не меняются, все три алгоритма поиска более эффективны, чем повторные поиски A*. D* и его варианты широко использовались для мобильного робота и автономного транспортного средства навигации. Современные системы обычно основаны на облегчённом, а не на оригинальном или сфокусированном D*. Фактически, даже лаборатория Стенца в некоторых реализациях использует облегчённый, а не оригинальный D*. Такие навигационные системы включают в себя прототип системы, испытанный на марсоходах Opportunity и Spirit, и навигационную систему победителя конкурса DARPA Urban Challenge, оба разработанные в Университете Карнеги — Меллона. Оригинальный D* был представлен Энтони Стенцем в 1994 году. Название D* происходит от термина «Dynamic A*» (рус. «Динамический A*»), потому что алгоритм ведёт себя как A*, за исключением того, что стоимость дуги может изменяться по мере выполнения алгоритма. (ru)
- D* - може відноситись до одного з трьох наступних алгоритмів пошуку:
* Оригінальний D*, написаний Ентоні Стенцом, який є евристичним алгоритмом.
* Цілеспрямований D* (en. Focused D*) - евристичний алгоритм розроблений Ентоні Стенцом. Він поєднує ідеї A* і оригінального D*. Алгоритм з'явився як результат подальшого розвитку оригінального D*.
* Легкий D* (en. D* Lite) - розроблений Свеном Кьонігом та Максимом Ліхачовим евристичний алгоритм, який побудований на основі LPA* - алгоритмі, який поєднує ідеї А* та динамічного пошуку найкоротшого шляху з однієї вершини(en. Dynamic SWSF-FP). (uk)
|
| rdfs:comment
|
- Der D*-Algorithmus ist ein Suchalgorithmus. Es handelt sich um eine Erweiterung des A*-Algorithmus und somit einen direkten „Nachfahren“ des Dijkstra-Algorithmus. Sowohl A* als auch der Dijkstra-Algorithmus sind in ihrer Grundform unflexibel und können auf Veränderungen im Graphen während oder nach der Expansion nicht reagieren. In beiden Fällen kann der Anwender alle Ergebnisse verwerfen und nochmal von vorne beginnen. Gerade bei Arbeiten mit Robotern oder Agenten unter realen Bedingungen (begrenzte Sensorreichweite, unbekannte Umgebung) kommt es vor, dass große Karten ständig aktualisiert werden.Anthony Stentz entwickelte an der Carnegie Mellon University eine Möglichkeit, A* so zu modifizieren, dass er mit den neuen Anforderungen funktioniert. (de)
- D* - може відноситись до одного з трьох наступних алгоритмів пошуку:
* Оригінальний D*, написаний Ентоні Стенцом, який є евристичним алгоритмом.
* Цілеспрямований D* (en. Focused D*) - евристичний алгоритм розроблений Ентоні Стенцом. Він поєднує ідеї A* і оригінального D*. Алгоритм з'явився як результат подальшого розвитку оригінального D*.
* Легкий D* (en. D* Lite) - розроблений Свеном Кьонігом та Максимом Ліхачовим евристичний алгоритм, який побудований на основі LPA* - алгоритмі, який поєднує ідеї А* та динамічного пошуку найкоротшого шляху з однієї вершини(en. Dynamic SWSF-FP). (uk)
- D* (pronounced "D star") is any one of the following three related incremental search algorithms:
* The original D*, by Anthony Stentz, is an informed incremental search algorithm.
* Focused D* is an informed incremental heuristic search algorithm by Anthony Stentz that combines ideas of A* and the original D*. Focused D* resulted from a further development of the original D*.
* D* Lite is an incremental heuristic search algorithm by Sven Koenig and Maxim Likhachev that builds on LPA*, an incremental heuristic search algorithm that combines ideas of A* and Dynamic SWSF-FP. (en)
- D* (pronunciado "D estrella") es uno de los siguientes tres algoritmos de búsqueda incremental:
* El D* original, por Anthony Stentz, es un algoritmo de búsqueda incremental informada.
* D* Enfocado es un algoritmo heurístico de búsqueda incremental informada creado por Anthony Stentz que combina ideas de A* y el D* original. D* Enfocado es el resultado de un desarrollo adicional de D* original.
* D* Lite es un algoritmo heurístico de búsqueda incremental creado por Sven Koenig y Maxim Likhachev que se basa en LPA*, combina ideas de A* y Dynamic SWSF-FP. (es)
- L'algorithme D* (qui se prononce D étoile ou D star à l'anglaise) recouvre un ensemble de trois algorithmes de recherche incrémentale heuristique suivants :
* L'algorithme original D* (original D*), de Anthony Stentz, est un algorithme de recherche incrémentale informé.
* L'algorithme Focused D* (ou D* focalisé) est un algoritme de recherche incrémentale informé heuristique de Anthony Stentz qui combine des idées de A* et de l'algorithme original D*. L'algorithme D* focalisé résulte d'un développement plus poussé de l'algorithme D* d'origine.
* L'algorithme D* Lite (ou D* léger) est un algorithme de recherche incremental heuristique de et Maxim Likhachev qui s'appuie sur , un algorithme de recherche incrementale heuristique qui combine les idées de A* et Dynamic SWSF-FP. (fr)
- Алгоритм поиска D* (произносится как «Ди стар») — это любой из трёх связанных :
* Оригинальный алгоритм D* Энтони Стенца — это информированный алгоритм инкрементного поиска.
* Сфокусированный D* — это алгоритм инкрементного эвристического поиска, разработанный Энтони Стенцем, который сочетает в себе идеи A* и оригинального D*. Сфокусированный D* возник в результате дальнейшего развития оригинального D*.
* Облегчённый D* — это алгоритм инкрементального эвристического поиска, созданный Свеном Кёнигом и Максимом Лихачёвым, который основан на LPA*, алгоритме инкрементального эвристического поиска, объединяющем идеи алгоритма поиска A* и динамического SWSF-FP. (ru)
|
