| Property |
Value |
| dbo:abstract
|
- 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)
- 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)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13738 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- 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)
- 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)
|
| rdfs:label
|
- Algorithme D* (fr)
- D* (en)
- Алгоритм поиска D* (ru)
- Алгоритм пошуку D* (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
