Lazy Search algoritmer kan effektivt lösa problem där kantutvärdering är flaskhalsen i beräkningen, som är fallet för robotisk rörelseplanering. Den optimala algoritmen i denna klass, LazySP, begränsar lazily kanten utvärdering till endast den kortaste vägen. Att göra så kommer på bekostnad av sökinsatser, dvs., LazySP måste kompilera om sökträdet varje gång en kant befinns vara ogiltig. Detta blir oöverkomligt dyrt när man har att göra med stora grafer eller mycket belamrade miljöer. Vår nyckelinsikt är behovet av att balansera både kantutvärdering och sökinsats för att minimera den totala planeringstiden. Vårt bidrag är tvåfaldigt. För det första föreslår vi ett ramverk, Generalized Lazy Search (GLS), som sömlöst växlar mellan sökning och utvärdering för att förhindra bortkastade insatser. Vi visar att för ett val av växel, GLS är bevisligen effektivare än LazySP. För det andra utnyttjar vi tidigare erfarenhet av kantsannolikhet för att härleda GLS-policyer som minimerar förväntad planeringstid. Vi visar att GLS utrustade med sådana tidigare betydligt överträffar konkurrenskraftiga baslinjer för många simulerade miljöer i R 2, SE(2) och 7-DoF manipulation.
GLS REF använder tidigare för att snabbt ogiltigförklara subpater tills den kortaste sökvägen hittas.
Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-based Toggles
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Engineering']}