ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı D wiki: info, historia y vídeos

videos internet

salud  


D* (pronunciado "D estrella") es uno de los próximos 3 algoritmos de busca incremental:



  • El D* original, por Anthony Stentz, es un algoritmo de busca incremental informada.
  • D* Enfocado es un algoritmo heurístico de busca incremental informada creado por Anthony Stentz que combina ideas de A* y el D* original. D* Enfocado es el resultado de un desarrollo auxiliar de D* original.
  • D* Lite es un algoritmo heurístico de busca incremental creado por Sven Koenig y Maxim Likhachev que se fundamenta en LPA*, combina ideas de A* y Dynamic SWSF-formación profesional.

Los 3 algoritmos de busca resuelven exactamente los mismos inconvenientes de planificación de senda basada en la suposición, incluyendo la planificación con la suposición de espacio libre, donde un robot debe navegar hasta las coordenadas de un fin dado en un terreno ignoto. Hace suposiciones sobre la parte ignota del terreno (por ejemplo: que no contiene obstáculos) y halla un camino más corto desde sus coordenadas actuales hasta la meta bajo estas suposiciones. El robot entonces prosigue el camino. Cuando se observa nueva información del mapa (como obstáculos anteriormente ignotos), se agrega la información a su mapa y, si es preciso, planea el nuevo camino más corto desde sus coordenadas actuales a las coordenadas del objetivo determinado. Se repite el proceso hasta el momento en que llega a las coordenadas del objetivo o bien determina que no se puede llegar a las coordenadas del objetivo. Al atravesar terrenos ignotos, nuevos obstáculos se pueden descubrir habitualmente, con lo que esta nueva planificación debe ser veloz. Los algorítmos de busca (heurística) incremental aceleran las buscas de secuencias de inconvenientes de busca afines a través de el empleo de la experiencia con los inconvenientes precedentes para apresurar la busca de la presente. Suponiendo que las coordenadas del objetivo no cambian, los 3 algoritmos de busca son más eficaces que las reiteradas buscas A*.


D* y sus variaciones han sido extensamente usados para robots móviles y navegación de automóviles autónomos. Los sistemas actuales se fundamentan generalmente en D* Lite en vez del D* original o bien D* Enfocado. En verdad, aun el laboratorio de Stentz usa D* Lite en vez de D* en ciertas implementaciones. Semejantes sistemas para la navegación incluyen un sistema prototipo probado en Marte en los astromóviles Opportunity y Spirit y en el sistema para la 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 mil novecientos noventa y cuatro. El nombre de D* viene del término "Dynamic A*", puesto que el algoritmo se comporta como A* salvo que los costos de los arcos pueden mudar conforme se ejecuta el algoritmo.


El funcionamiento básico de D* se describe ahora.


Al igual que el algoritmo de Dijkstra y A*, D* sostiene una lista de nodos para ser evaluados, famosa como la "lista abierta". Los nodos están marcados por tener uno de múltiples estados:



  • NUEVO, lo que quiere decir que jamás ha sido puesto en la lista abierta
  • ABIERTO, lo que quiere decir que se halla hoy día en la lista abierta
  • CERRADO, lo que quiere decir que ya no está en la lista abierta
  • SUPERIOR, señalando su costo es más alto que la última vez que estaba en la lista abierta
  • INFERIOR, señalando su costo es menor que la última vez que estaba en la lista abierta

El algoritmo marcha a través de la selección iterativa de un nodo de la lista abierta y evaluándolo. Ahora, extiende los cambios del nodo a todos y cada uno de los nodos vecinos y los pone en la lista abierta. Este proceso de propagación se llama "expansión". En contraste a A*, que prosigue el camino de principio a fin, D* empieza por buscar cara atrás desde el nodo objetivo. Cada nodo expandido tiene un backpointer que se refiere al siguiente nodo que conduce al objetivo, y cada nodo conoce el costo preciso al objetivo. Cuando el nodo de partida es el próximo nodo a expandirse, el algoritmo para, y el camino cara la meta se puede localizar, sencillamente siguiendo los backpointers.


Manejo de obstáculos


Cuando se advierte una obstrucción durante la trayectoria prevista, todos y cada uno de los puntos que se ven perjudicados se ponen nuevamente en la lista abierta, esta vez marcados a SUPERIOR. Ya antes de marcarlos a SUPERIOR se aumenta los costos, no obstante, el algoritmo verifica sus vecinos y examina si se puede reducir el costo del nodo. Si no, el estado SUPERIOR se extiende a todos y cada uno de los descendientes de los nodos, esto es, los nodos que tienen backpointers a ella. Estos nodos se valoran entonces, y el estado SUPERIOR se transmite, formando una onda. En el momento en que un nodo SUPERIOR se puede reducir, su backpointer se actualiza y pasa al estado LOWER a sus vecinos. Estas ondas de estados SUPERIOR y LOWER son el corazón de D*.


En este instante, se evita que una serie de otros puntos sean "tocados" por las ondas. El algoritmo, por lo tanto, solo ha trabajado en los puntos que se ven perjudicados por el cambio de los costos.


Ocurrencia de algún deadlock


Esta vez, el deadlock no puede cancelarse con tanta elegancia. Desde ninguno de los puntos se puede localizar una nueva senda mediante un vecino para el destino, por consiguiente, prosiguen extendiendo su incremento de costos. Solo fuera del canal se pueden hallar puntos, que pueden llevar al destino mediante una senda viable. Esto trata de de qué forma se desarrollan 2 ondas LOWER, que expanden puntos marcados inaccesibles con nueva información de la senda.


Como su nombre señala, D* Enfocado es una extensión de D* que usa una heurística para enfocar la propagación de SUPERIOR y también INFERIOR cara el robot. De este modo, solo los estados que importan son actualizados, de igual manera que A* solo calcula los costos para ciertos nodos.


D * Lite no se fundamenta en el D* original o bien D* Enfocado, mas incorpora exactamente el mismo comportamiento. Es más simple de comprender y se puede incorporar en un menor número de líneas de código, de ahí el nombre de "D* Lite". En lo que se refiere al desempeño, es tan bueno o bien mejor que D* Enfocado. D* Lite se fundamenta en Lifelong Planning A*, que fue presentado por Koenig y Likhachev unos años ya antes. D* Lite


Para D *, es esencial distinguir entre los costos actuales y costos mínimos. El primero es solo esencial en el instante de la recolección y el último es esencial, puesto que ordena la lista abierta. La función que devuelve el costo mínimo es siempre y en toda circunstancia el menor costo para el punto actual, en tanto que es la primera entrada de la lista abierta.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı D wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas