Theta*

Theta* är en vägplaneringsalgoritm för valfri vinkel som är baserad på A*-sökalgoritmen . Den kan hitta nästan optimala banor med körtider som är jämförbara med A*.

Beskrivning

För den enklaste versionen av Theta* är huvudslingan ungefär densamma som A*. Den enda skillnaden är ${\displaystyle {\text{update}}\_{\text{vertex}}()}-$ funktionen. Jämfört med A* behöver inte föräldern till en nod i Theta* vara en granne till noden så länge det finns en siktlinje mellan de två noderna. ^{[ citat behövs ]}

Pseudokod

Anpassad från.

  
    
      0
      
    
    
      
       
    
    
    
      
        
          
           
             
        
            
        
                
                    
                    
                    
                      
                      
                 
     
            
    
  
    
      
        
        
              
            
                 
              
               
                
               
    
        
        
        
              
                 
              
               
                
               

 
      
    
    
       
        
    
          funktion  theta  *  (  start  ,  mål  )  // Denna huvudslinga är densamma som A*  gScore  (  start  )  :=  förälder  (  start  )  :=  start  // Initiering av öppna och slutna set. Den öppna uppsättningen initieras   // med startnoden och en initial kostnad  öppen  :=  {}  öppen  .  infoga  (  start  ,  gScore  (  start  )  +  heuristic  (  start  ))  // gScore(nod) är det aktuella kortaste avståndet från startnoden till noden //  heuristic(nod) är det uppskattade avståndet för noden från målnoden  // där finns många alternativ för heuristiken som euklidisk eller Manhattan  stängd  :=  {}  medan  öppen  inte  är  tom  s  :=  öppen  .  pop  (  )  om  s  =  målretur  reconstruct_path  (  s  )  closed  .  push  (  s  )  för  varje  granne  till  s  // Slinga genom varje omedelbar granne till s  om  granne  inte  är  stängd  om  granne  inte  är  öppen  // Initiera värden för granne om det  // inte redan finns i den öppna listan  gScore  (  granne  )  : =  oändligt  förälder  (  granne  )  :=  Null  uppdatering_vertex  (  s  ,  granne  )  returnerar  Null  funktion  update_vertex  (  s  ,  granne  ) // Den här   delen  av algoritmen är den huvudsakliga skillnaden mellan A* och Theta  *  om  linje_of_sight  (  förälder  ,  granne  )  )  // Om det finns en siktlinje mellan förälder(ar) och granne  // ignorera sedan s och använd sökvägen från förälder(ar) till granne  om  gScore  (  förälder  (  s  ))  +  c  (  parent  (  s  )  ,  granne  )  <  gScore  (  granne  )  // c(s, granne) är det euklidiska avståndet från s till granne  gScore  (  granne  )  :=  gPoäng  (  förälder  (  ar  ))  +  c  (  förälder  (  ar  )  ,  granne  )  förälder  (  granne  )  :=  förälder  (  er  )  om  granne  i  öppet  öppet  .  ta bort  (  granne  )  öppna  .  infoga  (  granne  ,  gScore  (  granne  )  +  heuristisk  (  granne  ))  else  // Om längden på vägen från start till s och från s till //  granne är kortare än det kortaste för närvarande kända avståndet  // från start till granne, då uppdatera noden med det nya avståndet  om  gScore  (  s  )  +  c  (  s  ,  granne  )  <  gScore  (  granne  )  gScore  (  granne  )  :=  gScore  (  s  )  +  c  (  s  ,  granne  )  förälder  (  granne  )  :=  s  om  granne  i  öppen  öppen  .  ta bort  (  granne  )  öppna  .  infoga  (  granne  ,  gScore  (  granne  )  +  heuristisk  (  granne  ))  funktion  reconstruct_path  (  s  )  total_path  =  {s}  // Detta kommer rekursivt att rekonstruera sökvägen från målnoden //  tills startnoden nås  om  förälder  (  ar  )  !  =  s  total_sökväg  .  push  (  reconstruct_path  (  parent  (  s  )))  annars  returnerar  total_path

Varianter

Följande varianter av algoritmen finns: ^{[ citat behövs ]}

Lazy Theta* – Nodexpansionerna är försenade, vilket resulterar i färre siktlinjekontroller
Incremental Phi* – En modifiering av Theta* som möjliggör dynamisk vägplanering liknande D*

Se även