D*

Den här artikeln handlar om en sökalgoritm. Se D-STAR för specifikationen för digital röst och dataprotokoll . För den fysiska kvantiteten, se Specifik detektivitet . För den subatomära partikeln, se hexaquark .

D* (uttalas "D-stjärna") är någon av följande tre relaterade inkrementella sökalgoritmer :

  • Den ursprungliga D*, av Anthony Stentz, är en informerad inkrementell sökalgoritm.
  • Focused D* är en informerad inkrementell heuristisk sökalgoritm av Anthony Stentz som kombinerar idéer om A* och den ursprungliga D*. Fokuserad D* resulterade från en vidareutveckling av den ursprungliga D*.
  • D* Lite är en inkrementell heuristisk sökalgoritm av Sven Koenig och Maxim Likhachev som bygger på LPA* , en inkrementell heuristisk sökalgoritm som kombinerar idéer om A* och Dynamic SWSF-FP.

Alla tre sökalgoritmerna löser samma antagandebaserade vägplaneringsproblem , inklusive planering med antagandet om fritt utrymme, där en robot måste navigera till givna målkoordinater i okänd terräng. Den gör antaganden om den okända delen av terrängen (till exempel att den inte innehåller några hinder) och hittar en kortaste väg från sina nuvarande koordinater till målkoordinaterna under dessa antaganden. Roboten följer sedan vägen. När den observerar ny kartinformation (som tidigare okända hinder), lägger den till informationen på kartan och planerar vid behov om en ny kortaste väg från dess nuvarande koordinater till de givna målkoordinaterna. Den upprepar processen tills den når målkoordinaterna eller fastställer att målkoordinaterna inte kan nås. När du korsar okänd terräng kan nya hinder upptäckas ofta, så denna omplanering måste gå snabbt. Inkrementella (heuristiska) sökalgoritmer påskyndar sökningar efter sekvenser av liknande sökproblem genom att använda erfarenhet av tidigare problem för att påskynda sökningen efter det aktuella. Om man antar att målkoordinaterna inte ändras, är alla tre sökalgoritmerna mer effektiva än upprepade A*-sökningar.

D* och dess varianter har använts i stor utsträckning för mobil robot- och autonoma fordonsnavigering . Nuvarande system är vanligtvis baserade på D* Lite snarare än original D* eller Focused D*. Faktum är att även Stentz labb använder D* Lite snarare än D* i vissa implementeringar. Sådana navigationssystem inkluderar ett prototypsystem som testats på Mars rovers Opportunity och Spirit och navigationssystemet för det vinnande bidraget i DARPA Urban Challenge, båda utvecklade vid Carnegie Mellon University .

Den ursprungliga D* introducerades av Anthony Stentz 1994. Namnet D* kommer från termen "Dynamic A*", eftersom algoritmen beter sig som A* förutom att bågkostnaderna kan ändras när algoritmen körs.

Drift

Den grundläggande funktionen för D* beskrivs nedan.

Liksom Dijkstras algoritm och A*, upprätthåller D* en lista över noder som ska utvärderas, känd som "OPEN-listan". Noder är markerade som att ha ett av flera tillstånd:

  • NY, vilket betyder att den aldrig har placerats på OPEN-listan
  • ÖPPEN, vilket betyder att den för närvarande finns på ÖPPEN-listan
  • STÄNGD, vilket betyder att den inte längre finns på ÖPPEN-listan
  • RAISE, vilket indikerar att kostnaden är högre än förra gången den var på OPEN-listan
  • LÄGRE, vilket indikerar att kostnaden är lägre än förra gången den var på OPEN-listan

Expansion

Algoritmen fungerar genom att iterativt välja en nod från OPEN-listan och utvärdera den. Den sprider sedan nodens ändringar till alla närliggande noder och placerar dem på OPEN-listan. Denna förökningsprocess kallas "expansion". Till skillnad från kanoniskt A*, som följer banan från början till slut, börjar D* med att söka bakåt från målnoden. Detta betyder att algoritmen faktiskt beräknar den optimala A*-vägen för varje möjlig startnod. Varje expanderad nod har en bakåtpekare som refererar till nästa nod som leder till målet, och varje nod vet den exakta kostnaden för målet. När startnoden är nästa nod som ska utökas, är algoritmen klar, och vägen till målet kan hittas genom att helt enkelt följa bakåtpekarna.

  • Expansion in progress. The finish node (yellow) is in the middle of the top row of points, the start node is in the middle of the bottom row. Red indicates an obstacle; black/blue indicates expanded nodes (brightness indicating cost). Green indicates nodes which are being expanded.

    Utbyggnad pågår. Målnoden (gul) är i mitten av den översta raden av punkter, startnoden är i mitten av den nedre raden. Rött indikerar ett hinder; svart/blått indikerar utökade noder (ljusstyrka indikerar kostnad). Grönt indikerar noder som utökas.

  • Expansion finished. The path is indicated in cyan.

    Utbyggnaden avslutad. Vägen anges i cyan.

Hinderhantering

När ett hinder upptäcks längs den avsedda vägen placeras alla de punkter som påverkas återigen på ÖPPEN-listan, denna gång märkt HÖJ. Innan en RAISED nod ökar i kostnad kontrollerar algoritmen dock sina grannar och undersöker om den kan minska nodens kostnad. Om inte, sprids RAISE-tillståndet till alla nodernas avkomlingar, det vill säga noder som har bakåtpekare till sig. Dessa noder utvärderas sedan och RAISE-tillståndet förs vidare och bildar en våg. När en HÖJD nod kan reduceras uppdateras dess bakåtpekare och skickar det LÄGRE tillståndet till sina grannar. Dessa vågor av RAISE och LOWER tillstånd är hjärtat av D*.

Vid det här laget förhindras en hel rad andra punkter från att "berördas" av vågorna. Algoritmen har därför bara arbetat på de punkter som påverkas av kostnadsförändringar.

  • An obstacle has been added (red) and nodes marked RAISE (yellow).

    Ett hinder har lagts till (rött) och noder märkt RAISE (gul).

  • Expansion in progress. Yellow indicates nodes marked RAISE, green indicates nodes marked LOWER.

    Utbyggnad pågår. Gult indikerar noder markerade HÖJ, grönt indikerar noder markerade LOWER.

Ytterligare ett dödläge inträffar

Den här gången går dödläget inte förbi så elegant. Ingen av punkterna kan hitta en ny rutt via en granne till destinationen. Därför fortsätter de att sprida sin kostnadsökning. Endast punkter utanför kanalen kan hittas, vilket kan leda till destination via en gångbar rutt. Det är så två lägre vågor utvecklas, som expanderar som punkter markerade som ouppnåeliga med ny ruttinformation.

  • Channel blocked by additional obstacles (red)

    Kanal blockerad av ytterligare hinder (röd)

  • Expansion in progress (Raise wave in yellow, Lower wave in green)

    Expansion pågår (Höj våg i gult, lägre våg i grönt)

  • New path found (cyan)

    Ny sökväg hittades (cyan)

Pseudokod 

  
      
    
 while  (  !  openList  .  isEmpty  ())  {  point  =  openList  .  getFirst  ();  expandera  (  punkt  );  }

Bygga ut 

  
       
     
         
          
                
                
                
              
                  
                    
                    
                    
                
            
          
              
                
                
                
            
        
     void  expand  (  currentPoint  )  {  boolean  isRaise  =  isRaise  (  currentPoint  );  dubbel  kostnad  ;  för  varje  (  granne  i  aktuellPoint  .  getNeighbors  ())  {  if  (  isRaise  )  {  if  (  neighbor  .  nextPoint  ==  currentPoint  )  {  neighbor  .  setNextPointAndUpdateCost  (  currentPoint  );  öppen listan  .  add  (  granne  );  }  annat  {  kostnad  =  granne  .  calculateCostVia  (  currentPoint  );  if  (  kostnad  <  granne  .  getCost  ())  {  currentPoint  .  setMinimumCostToCurrentCost  ();  öppen listan  .  add  (  currentPoint  );  }  }  }  annat  {  kostnad  =  granne  .  calculateCostVia  (  currentPoint  );  if  (  kostnad  <  granne  .  getCost  ())  {  granne  .  setNextPointAndUpdateCost  (  currentPoint  );  öppen listan  .  add  (  granne  );  }  }  }  }

Kolla efter höjning 

  
     
        
            
              
                
                
            
        
    
       
 boolean  isRaise  (  point  )  {  double  cost  ;  if  (  punkt  .  getCurrentCost  ()  >  punkt  .  getMinimumCost  ())  {  för  varje  (  granne  i  punkt  .  getNeighbors  ())  {  kostnad  =  poäng  .  calculateCostVia  (  granne  );  if  (  kostnad  <  poäng  .  getCurrentCost  ())  {  point  .  setNextPointAndUpdateCost  (  granne  );  }  }  }  returpunkt  .  _  getCurrentCost  ()  >  punkt  .  getMinimumCost  ();  }

Varianter

Fokuserad D*

Som namnet antyder är Focused D* en förlängning av D* som använder en heuristik för att fokusera spridningen av RAISE och LOWER mot roboten. På detta sätt uppdateras bara de tillstånd som spelar roll, på samma sätt som A* endast beräknar kostnader för några av noderna.

D* Lite

D* Lite är inte baserad på den ursprungliga D* eller Focused D*, men implementerar samma beteende. Det är enklare att förstå och kan implementeras i färre rader kod, därav namnet "D* Lite". Prestandamässigt är den lika bra som eller bättre än Focused D*. D* Lite är baserad på Lifelong Planning A* , som introducerades av Koenig och Likhachev några år tidigare. D* Lite

Minimikostnad kontra nuvarande kostnad

För D* är det viktigt att skilja mellan nuvarande och minimikostnader. Det förra är bara viktigt vid tidpunkten för insamlingen och det senare är kritiskt eftersom det sorterar OpenList. Funktionen som returnerar minimikostnaden är alltid den lägsta kostnaden till den aktuella punkten eftersom det är den första posten i OpenList.

  1. ^   Stentz, Anthony (1994), "Optimal och effektiv vägplanering för delvis kända miljöer", Proceedings of the International Conference on Robotics and Automation : 3310–3317, CiteSeerX 10.1.1.15.3683
  2. ^   Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", Proceedings of the International Joint Conference on Artificial Intelligence : 1652–1659, CiteSeerX 10.1.1.41.8257
  3. ^ Hart, P.; Nilsson, N.; Raphael, B. (1968), "En formell grund för den heuristiska bestämning av minimikostnadsvägar", IEEE Trans. Syst. Science and Cybernetics , SSC-4 (2): 100–107, doi : 10.1109/TSSC.1968.300136
  4. ^   Koenig, S.; Likhachev, M. (2005), "Fast Replanning for Navigation in Unknown Terrain", Transactions on Robotics , 21 (3): 354–363, CiteSeerX 10.1.1.65.5979 , doi : 10.1109/tro.2004.838026
  5. ^ Koenig, S.; Likhachev, M.; Furcy, D. (2004), "Lifelong Planning A*", Artificiell intelligens , 155 (1–2): 93–146, doi : 10.1016/j.artint.2003.12.001
  6. ^   Ramalingam, G.; Reps, T. (1996), "An incremental algorithm for a generalization of the shortest-path problem", Journal of Algorithms , 21 (2): 267–305, CiteSeerX 10.1.1.3.7926 , doi : 10.1006/jagm.069
  7. ^ Koenig, S.; Smirnov, Y.; Tovey, C. (2003), "Performance Bounds for Planning in Unknown Terrain", Artificial Intelligence , 147 (1–2): 253–279, doi : 10.1016/s0004-3702(03)00062-6
  8. ^ Wooden, D. (2006). Grafbaserad vägplanering för mobila robotar ( uppsats). Georgia Institute of Technology.
  9. ^   Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", Proceedings of the International Joint Conference on Artificial Intelligence : 1652–1659, CiteSeerX 10.1.1.41.8257
  10. ^   Murphy, Robin R. (2019). Introduktion till AI-robotik (2:a upplagan). Bradford böcker. Punkt 14.5.2. ISBN 978-0262038485 .

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=D*&oldid=1141987744 "