Sökmetoder i realtid lämpar sig för uppgifter där agenten interagerar med en till en början okänd miljö i realtid. I sådana samtidiga planerings- och inlärningsproblem, måste agenten välja sina åtgärder på en begränsad tid, samtidigt som den bara känner en lokal del av miljön centrerad på agentens nuvarande plats. Realtid heuristiska sökagenter väljer åtgärder med hjälp av en begränsad lookahead sökning och utvärdera gränsstater med en heuristisk funktion. Genom upprepade erfarenheter förfinar de staters heuristiska värden för att undvika oändliga slingor och för att konvergera till bättre lösningar. Den stora spridningen av sådana inställningar i autonom programvara och hårdvaruagenter har lett till en explosion av realtidssökningsalgoritmer under de senaste två decennierna. Inte bara är en potentiell användare konfronteras med en Hodgepodge av algoritmer, men han står också inför valet av kontrollparametrar som de använder. I det här dokumentet tar vi upp båda problemen. Det första bidraget är en introduktion av en enkel tre-parameter ram (kallad LRTS) som extraherar kärnidéer bakom många befintliga algoritmer. Vi bevisar sedan att LRTA*, LRTA*, SLA* och γ-Trap algoritmer är speciella fall av vårt ramverk. Därför är de enhetliga och utökade med ytterligare funktioner. För det andra bevisar vi fullständighet och konvergens av alla algoritmer som omfattas av LRTS-ramverket. För det tredje visar vi flera övre gränser för kontrollparametrar och lösningskvalitet. Slutligen analyserar vi inflytandet av de tre kontrollparametrarna empiriskt i de realistiska skalbara domänerna för realtidsnavigering på till en början okända kartor från ett kommersiellt rollspel samt routing i ad hoc-sensornätverk. I detta dokument överväger vi ett problem med samtidig planering och lärande. En motiverande tillämpning ligger med navigering på en till en början okänd karta under realtidsbegränsningar. Tänk till exempel på att en robot kör till jobbet varje morgon. Tänk dig roboten att vara en nykomling till staden. Den första vägen roboten hittar kanske inte är optimal eftersom trafikstockningar, vägförhållanden, och andra faktorer är till en början okända. Med tidens gång, fortsätter roboten att lära sig och så småningom konvergerar till en nästan optimal pendla. Observera att planering och lärande sker medan roboten kör och därför är föremål för tidsbegränsningar. Dagens mobila robotar plågas ofta av lokala problem och maktbegränsningar, men deras simuleringsmotdelar tillåter redan forskare att fokusera på planerings- och inlärningsproblem. Till exempel RoboCup Rescue-simuleringsligan (Kitano, Tadokoro, Noda, Matsubara, Takahashi, Shinjou, & Shimada, 1999) kräver planering och lärande i realtid med flera agenter som kartlägger en okänd terräng. Pathfinding görs i realtid som olika kriser, inklusive brandspridning och mänskliga offer fångade i spillror, framsteg medan agenter planerar. På samma sätt, många nuvarande generation realtid strategi spel använder en tidigare kända kartor. Full kunskap om kartorna möjliggör fullständiga sökmetoder som A* (Hart, Nilsson, & Raphael, c 2006 AI Access Foundation. Alla rättigheter förbehållna. BULITKO & LEE 1968) och Dijkstra algoritm (Dijkstra, 1959). Med hjälp av tidigare tillgång till kartorna kan man i förväg beräkna olika data för att snabba upp on-line-navigeringen. Exempel på sådana data är synbarhetsgrafer (Woodcock, 2000), influenskartor (Potter, 2000), rymdtriangulation (Kallmann, Bieri, & Thalmann, 2003), statliga abstraktionshierarkier (Holte, Drummond, Perez, Zimmer, & MacDonald, 1994; Holte, 1996; Botea, Müller, & Schaeffer, 2004) och vägwaypoints (Reece, Krauss, & Dumanoir, 2000). De kommande generationerna av kommersiella och akademiska spel (Buro, 2002) kommer dock att kräva att agenten hanterar initialt okända kartor via prospektering och lärande under spelet, och kommer därför i hög grad att begränsa tillämpligheten av fullständiga sökalgoritmer och pre-beräkningstekniker. Inkrementella sökmetoder såsom dynamiska A* (D*) (Stenz, 1995) och D* Lite (Koenig & Likhachev, 2002) kan hantera initialt okända kartor och används allmänt i robotik, inklusive DARPA: s Unmanned Ground Vehicle program, Mars rover, och andra mobila robot prototyper (Herbert, McLachlan, & Chang, 1999; Thayer, Digney, Diaz, Stentz, Nabbe, & Hebert, 2000). De fungerar bra när robotens rörelser är långsamma med avseende på dess planeringshastighet (Koenig, 2004). I realtid strategispel, men AI motorn kan vara ansvarig för hundratals till tusentals agenter traversing en karta samtidigt och planeringskostnaden blir en viktig faktor. För att illustrera: även på den mindre skalan av den sexåriga "Age of Empires 2" (Ensemble-Studios, 1999), 60-70% av simuleringstiden spenderas i patologi (Potter, 2000). Detta ger upphov till följande frågor: 1. Hur kan planeringstiden per drag, och i synnerhet den första fördröjningen, minimeras så att varje agent rör sig smidigt och svarar på användarens önskemål nästan omedelbart? 2. Utgångspunkten är följande: Med tanke på realtidsutförande, lokal sensorisk information och till en början okänd terräng, hur kan agenten lära sig en nästan optimal väg och samtidigt minimera inlärningstiden och minnet som krävs? Resten av tidningen är organiserad enligt följande. Vi introducerar först en familj av realtidssökningsalgoritmer utformade för att ta itu med dessa frågor. Vi gör sedan det första bidraget genom att definiera en enkel parameteriserad ram som förenar och utökar flera populära realtidssökningsalgoritmer. Det andra bidraget ligger i en teoretisk analys av den resulterande ramen där vi bevisar konvergens och fullständighet samt flera resultatgränser. Slutligen utvärderar vi påverkan av kontrollparametrarna inom två olika områden: enkelagentnavigering i okända kartor och routing i ad hoc-sensornätverk. Detaljerad pseudokod som behövs för att omimplementera algoritmerna samt för att följa teoremproofen presenteras i bilaga A. Theorem proofs själva finns i bilaga B. Vi placerar vår kartläggning av realtid heuristisk söklitteratur inom ramen för agentcentrerad sökning (Koenig, 2001). Medan traditionella off-line sökmetoder först planera en väg från start till mål tillstånd och sedan flytta agenten längs vägen, agent-centrerad sökning interleaves planering och utförande. Dessutom är planeringen begränsad till de områden i sökområdet runt det aktuella tillståndet för agenten såsom den fysiska placeringen av en mobil robot eller nuvarande styrelseposition i ett spel. De agentcentrerade sökmetoderna uppfyller således dessa två krav: i) agenten befinner sig alltid i ett enda tillstånd som endast kan ändras genom att vidta åtgärder och därmed ådra sig kostnader för utförande; ii) agenten kan endast se staterna kring sitt nuvarande tillstånd. Realtidsheuristiska sökmetoder är en delmängd av agentcentrerade sökmetoder. De kännetecknas av följande två ytterligare egenskaper: i) planeringstiden per flyttning kan vara övre gräns för en användarbaserad konstant (därav i realtid); ii) de associerar en heuristisk funktion med varje tillstånd (därav heuristisk). Det tidigare kravet motiveras av behovet av att agera snabbt i kontrolluppgifter som att flyga en helikopter (Ng, Coates, Diel, Ganapathi, Schulte, Tse, Berger, & Liang, 2004) eller spela ett dataspel i realtid (Buro, 2002). Den senare egenskapen gör det möjligt för agenten att undvika oändliga cykler på en karta genom att lära sig de rätta avstånden från varje stat till måltillståndet. Till skillnad från att lära sig kartan och använda den för planering (Stenz, 1995; Koenig & Likhachev, 2002; Chimura & Tokoro, 1994; Sturtevant, 2005), förvärva högkvalitativa heuristiska värden kan agenten välja rätt åtgärd mycket snabbt och därmed förbättra sin reaktionstid. Med de heuristiska värdena kan agenten också välja nästa bästa åtgärd om det primära valet blir otillgängligt (t.ex. på grund av ett vägblock på kartan). Anmärkningsvärt, lärande tillstånd och stat-aktionsvärden är den rådande tekniken i Förstärkning Lärande (Sutton, 2005). Lära sig realtidssökning algoritmer, såsom LRTA* (Korf, 1990), interleave planering och genomförande i en on-line beslutsfattande inställning. Eftersom planeringstiden för varje åtgärd som utförs av agenten begränsas, kan dessa algoritmer användas som kontrollpolicy för autonoma agenter, även i en okänd och/eller icke-stationär miljö (Koenig & Simmons, 1998; Koenig, 1999; Ishida & Korf, 1991 Ishida, 1997). I synnerhet, förmågan att fatta beslut efter endast en småskalig lokal sökning gör dessa algoritmer väl lämpade för routing i storskaliga trådlösa nätverk av enkla sensorer och ställdon där varje nod är medveten endast om sina närliggande grannar och ingen global karta finns. I sådana scenarier, inte bara den begränsade mängden beräkning per nod passar den låga datorkraft och energikrav, men också nätverket kollektivt lär sig sin egen topologi över tid (Yu, Govindan, & Estrin, 2001; Shang, Fromherz, Zhang, & Crawford, 2003). Sedan den banbrytande LRTA* (Korf, 1990), forskning inom området lärande i realtid heuristisk sökning har utvecklats i flera större riktningar. Ishida och Korf (1991) undersökte ändringar av LRTA* för icke-stationära miljöer. Shimbo och Ishida (2003) studerade konvergens till suboptimala lösningar samt mekanismer för att begränsa mängden utforskning av statsrymder. Furcy och Koenig (2000) övervägde en annan inlärningsmekanism som påskyndade konvergensen. Russell och Wefald (1991) undersökte ett besluts-teoretiskt tillvägagångssätt för att balansera partiell planering och genomförande. Shue och Zamani (1993) och Bulitko (2004) föreslog en bakåtsträvande komponent som föreslog ytterligare ett sätt att kontrollera utforskningen av miljön. Observera att även om den ursprungliga LRTA* algoritmen kan ses som ett specialfall av realtids dynamisk programmering (Barto, Bradtke, & Singh, 1995), i allmänhet, realtid heuristiska sökmetoder har flera anmärkningsvärda skillnader från förstärkande inlärningsmetoder. För det första antar de vanligtvis en deterministisk miljö och utnyttjar därmed mer aggressiva regler för värdeuppdatering. För det andra, de använder icke-triviala initiala heuristik och kan konvergera ännu snabbare när en sådan heuristisk är tillåtlig (Pearl, 1984) genom att aldrig minska heuristiska värden av stater. För det tredje använder sig de heuristiska sökmetoderna i realtid ofta av mer omfattande och sofistikerade lokala sökmetoder än den politik som ofta används för att stärka inlärningen. Exempel inkluderar dynamiskt utvalda lookahead sökutrymme i DTA* (Russell & Wefald, 1991), ytterligare heuristisk för slipsbrytande i FALCONS (Furcy & Koenig, 2000), och heuristiska övre gränser för säker utforskning i avgränsade LRTA* (Shimbo & Ishida, 2003). Detta förbättrar kvaliteten på beslutsfattandet genom att kompensera för felaktigheter i den heuristiska funktionen och påskyndar inlärningsprocessen. Slutligen, backtracking förlängningar (Shue & Zamani, 1993; Bulitko, 2004) ger agenten en annan mekanism för att upprätthålla konsekvensen i sin heuristiska. Mångfalden av lärande realtidssökningsalgoritmer (LRTA*, LRTA*, δ-LRTA*, FAL-CONS, eFALCONS, SLA*, γ-Trap, SLA*T, DTA*, etc.) tillgängliga för användaren kan vara desorienterande eftersom han måste besluta inte bara om algoritmen att använda utan också om algoritmparametrar som kan ha en stor inverkan på prestanda. Problemet kompliceras ytterligare av det faktum att empiriska studier har gjorts i olika testbäddar vilket gör resultaten ojämförbara direkt. För att illustrera detta: Furcy och Koenig (2000) samt Shimbo och Ishida (2003) verkar använda samma testbädd (den 8-pussel). Men deras resultat på samma algoritm (LRTA*) skiljer sig avsevärt åt. En närmare granskning visar att två olika målstater användes, vilket ledde till de stora skillnaderna i prestanda. För att förvärra dessa problem har de flesta prestandamått mätts med den myopiska lookaheadsökningen av djup ett. Detta är i motsats till spelande praxis där de flesta konkurrenskraftiga system får en betydande fördel av en djupare sökhorisont (Schaeffer, Culberson, Treloar, Knight, Lu, & Szafron, 1992; Hsu, Campbell, & Hoane, 1995; Buro, 1995). Vi tar ett steg mot en enhetlig syn på lärande i realtidssökning och bidrar med fyra bidrag. För det första introducerar vi ett enkelt treparametersramverk (LRTS) som inkluderar LRTA*, LRTA*, SLA* och γ-Trap som specialfall. En biprodukt av denna generalisering är en förlängning av de tre första algoritmerna till variabel djuplookahead. För det andra visar vi fullständighet och konvergens för alla kombinationer av parametrarna. För det tredje, vi bevisar icke-triviala teoretiska gränser på påverkan av parametrarna. För det fjärde presenterar vi en storskalig empirisk utvärdering inom praktiskt taget relevanta områden. I det här avsnittet introducerar vi formellt inställningarna för inlärning av sökproblem i realtid och de mätvärden vi kommer att använda. Definition 3.1 Sökutrymmet definieras som en tuple (S, A, c, s 0, Sg, h 0 ) där S är en ändlig uppsättning av stater, A är en ändlig uppsättning åtgärder, c : S × A → R + är kostnadsfunktionen med c (s, a) är den uppkomna kostnaden för att vidta åtgärder a i staten s, s 0 är det ursprungliga tillståndet, S g  på S är uppsättningen av måltillstånd, och h 0 är den ursprungliga heuristiska (t.ex. Manhattan avstånd). Vi antar antaganden Shue och Zamani (1993), Shimbo och Ishida (2003) att (i) för varje åtgärd i varje stat finns det en omvänd åtgärd (eventuellt med en annan kostnad), (ii) varje tillämplig åtgärd leder till en annan stat (dvs. inga själv-loops), och (iii) minst ett mål tillstånd i S g kan nås från s 0. Antagande (i) behövs för den backtracking mekanism som används i SLA* (Shue & Zamani, 1993). Den innehåller många kombinatoriska och vägplaneringsproblem. Dess tillämplighet på domäner där reversering av en åtgärd kan kräva en icke-trivial sekvens av åtgärder är föremål för framtida forskning. Antagande (ii) antas för bevis enkelhetens skull. Med andra ord, de resultat som presenteras i detta dokument håller även om själv-loops (av positiva kostnader) är närvarande. Som med alla realtidssökningsalgoritmer vi enar antar vi att miljön är stationär och deterministisk. Utbyggnad av våra algoritmer på dynamiska/stochastiska domäner är ett ämne för aktuell forskning. Definition 3.2 Verkställigheten kostnaden för att resa från staten s 1 till staten s 2 betecknar av dist (s 1, s 2 ) definieras som den minsta kumulativa kostnaden för utförande agenten är att ådra sig genom att resa från s 1 till s 2. Genom hela tidningen kommer vi att anta att dist uppfyller standard triangeln ojämlikhet: Definition 3.3 Sökagenter fungerar genom att börja i en fast startstat s 0 och genomföra åtgärder som föreslås av deras kontrollpolicy. En rättegång definieras som en sekvens av tillstånd algoritmbesök mellan starttillståndet och det första måltillståndet den möter. När en rättegång är klar, återställs agenten till starttillståndet och nästa försök börjar. Slutlig prövning definieras som den första prövning där ingen inlärning (dvs. uppdateringar av den heuristiska funktionen) inträffar. 1 En konvergerande körning är sekvensen av försök från den första rättegången till den slutliga rättegången. Varje problem instans är helt specificerad av sökområdet som inkluderar start-och måltillstånd. Agenten drivs fram till konvergens och följande statistik samlas in: kostnaden för genomförandekonvergens är summan av kostnaderna för genomförandet av de åtgärder som vidtagits av agenten under konvergensprocessen (dvs. under konvergensperioden); planeringskostnaden är den genomsnittliga kostnaden för planering per åtgärd under konvergensprocessen. Planeringskostnaden för en åtgärd är det antal stater som agenten anser sig besluta om att vidta åtgärden; den totala konvergenskostnaden är den totala planeringskonvergenskostnaden för alla åtgärder under konvergensen plus genomförandekonvergenskostnader som skalas upp av en faktor som kallas "planeringshastighet". Skalningsfaktorn motsvarar den mängd planering (mätt i antalet berörda noder) som agenten skulle kunna göra i den tid det tar att utföra en enhet för resor. Till exempel, datorn ombord en AIBO robodog kan kunna planera med 10.000 stater i den tid det tar AIBO att passera 1 fot av avstånd på marken. På motsvarande sätt kommer planeringshastigheten att vara 10.000 tillstånd per fot. Detta är ett vanligt använt sätt att kombinera kostnader för utförande och planering till en enda metriska (Russell & Wefald, 1991; Koenig, 2004) ; 2 minne är den totala mängden minne (mätt i antalet tillståndsvärden) agenten som används för att lagra den heuristiska funktionen under konvergenskörningen. Observera att den initiala heurismen vanligtvis representeras i en kompakt algoritmisk form i motsats till en tabell. Därför krävs minne för att lagra endast de heuristiska värden som modifieras under inlärning; första-flytta fördröjning (lag) är mängden planeringstid (mätt i millisekunder 3 ) agenten tar innan beslut om det första draget. Detta är ett viktigt mått i realtid strategispel, 1. Observera att om slumpmässiga slipsbrytande används, kan mer lärande faktiskt äga rum efter en inlärningsfri rättegång. Vi använder fasta slipsbrytande i hela detta papper för enkelhetens skull. 2. Utgångspunkten är följande: Observera att till skillnad från den totala planeringskostnaden ger den totala konvergenskostnaden oss möjlighet att modellera områden där vissa åtgärder är dyra oproportionerligt med sin körtid (t.ex. att ta skada genom att springa in i en vägg). Dessutom använder vi det vanliga sökramverket i realtid och utgår från att planering och utförande inte är samtidiga utan interleaved. 3. Vad är det som händer? Alla tidpunkter är tagna på en PowerMac G5 kör på 2 GHz. Apple gcc 3.3 kompilator används. BULITKO & LEE där hundratals till tusentals enheter kan laddas samtidigt och ändå måste reagera på användarens kommandon så snabbt som möjligt; suboptimaliteten hos den slutliga lösningen definieras som den procentandel genom vilken exekveringskostnaden för den slutliga prövningen överstiger den bästa möjliga lösningen. Till exempel, om en sökande agent hade kostnaden för avrättningen av 120 på den slutliga rättegången och den kortaste vägen har kostnaden för 100, är suboptimaliteten 20%. I tidningen illustrerar vi algoritmerna i två realistiska testbäddar: realtidsnavigering i okänd terräng och routing i ad hoc trådlösa sensornätverk. Den tidigare domänen är mer standard för enkelagentsökning och därför kommer vi att använda den i hela tidningen för att illustrera våra punkter. Den senare domänen är en relativ nykomling till området för realtid heuristisk sökning. Vi kommer att använda det senare i tidningen (avsnitt 8) för att visa hur lärande single-search metoder kan hantera en praktiskt taget viktig men annorlunda uppgift. Observera att båda domänerna har de önskade attributen listade i inledningen. Faktum är att i båda domänerna är statsrymden från början okänd, agenten befinner sig i ett enda nuvarande tillstånd som ska ändras genom verkställande åtgärder, agenten kan endast känna en lokal del av statsrymden centrerad på agentens nuvarande tillstånd, planeringstiden per åtgärd bör minimeras, och det finns upprepade prövningar. Agenten är uppgift att resa från start tillstånd (x s, y s ) till det enda måltillståndet (x g, y g ). Koordinaterna är på ett tvådimensionellt rektangulärt rutnät. I varje tillstånd finns upp till åtta drag tillgängliga som leder till de åtta närmaste grannarna. Varje rak rörelse (dvs., norr, söder, väster, öster) har en resekostnad på 1 medan varje diagonalt drag har en resekostnad på 2. Varje stat på kartan kan passeras eller ockuperas av en vägg. I det senare fallet kan agenten inte flytta in i det. Inledningsvis är kartan i sin helhet okänd för agenten. I varje tillstånd (x, y) agenten kan se status (bebodd / fri) i närheten av siktradien v: Den initiala heuristic vi använder är den så kallade oktile avstånd definieras som längden på en kortaste vägen mellan de två platserna om alla celler är går att passera. Det är en översättning av Manhattan avstånd till fallet med åtta drag och kan enkelt beräknas i en sluten form. Observera att klassisk A*-sökning inte är tillämplig på grund av en från början okänd karta. Särskilt är det omöjligt för agenten att planera sin väg genom tillstånd (x, y) om den inte antingen är placerad inom siktradien av staten eller har besökt detta tillstånd på en tidigare rättegång. En enkel lösning på detta problem är att generera den ursprungliga vägen under antagandet att de okända områdena på kartan innehåller inga ockuperade stater (det fria utrymmet antagande Koenig, Tovey, & Smirnov, 2003). Med oktilavståndet som heuristisk är den första stigen nära den raka linjen eftersom kartan antas vara tom. Agenten följer den befintliga vägen tills den går in i ett ockuperat tillstånd. Under resan uppdateras den utforskade delen av kartan i dess minne. När den nuvarande sökvägen är blockerad, anropas A* igen för att generera en ny komplett sökväg från nuvarande position till målet. Processen upprepas tills agenten anländer till målet. Den återställs sedan till starttillståndet och en ny rättegång börjar. Konvergensen upphör när inga nya stater ses. Fyra. Observera att denna ram enkelt kan utökas till fallet med flera start- och måltillstånd. För att öka planeringseffektiviteten har flera metoder för att återanvända information över efterföljande planeringsepisoder föreslagits. Två populära versioner är D* (Stenz, 1995) och D* Lite (Koenig & Likhachev, 2002). Kraftfulla som de är, dessa förbättringar minskar inte den första-flytta fördröjningen. Efter att agenten har fått destinationskoordinaterna måste den göra en A*-sökning från sin position till destinationen innan den kan förflytta sig. Även på små kartor kan förseningen bli betydande. Detta är i kontrast till LRTA* ( Korf, 1990), som endast utför en liten lokal sökning för att välja det första draget. Som ett resultat, flera order av magnitud fler agenter kan svara på en användares begäran i den tid det tar en A* agent. Eftersom dagens spel kringgår dessa problem genom att använda fullt observerbara kartor och precomputing extra data strukturer i förväg, genomför vi våra experiment i en forskningsprototyp, kallad Hierarchical Open Graph (HOG), utvecklad vid University of Alberta av Nathan Sturtevant. Det gör det möjligt att ladda kartor från kommersiella rollspel och realtid strategispel som Baldur's Gate (BioWare, 1999) och WarCraft III (Blizzard, 2002). Vi använder fem kartor i storlek från 214 × 192 tillstånd (varav 2765 är traverserbara) till 235 × 204 (med 16142 traverserbara tillstånd). Den största kartan visas i figur 1. Totalt 1000 problemfall på de fem kartorna valdes slumpmässigt så att deras kortaste stiglängder faller i de tio lådorna: 1-10, 11-20,..., 91-100 med 100 problem per bin. Vi kommer att använda denna svit med 1000 problem i hela tidningen.  I detta avsnitt kommer vi att presentera det primära bidraget från detta dokument - den enhetliga ramen för realtidsheuristisk sökning - på ett stegvist sätt. Nämligen, vi kommer att börja med basalgoritmen, LRTA*, och sedan analysera tre förlängningar: djupare lookahead, optimality vikt, och backtracking. Varje förlängning illustreras med ett handtrakat mikroexempel och empiriska resultat i realtidssökardomänen. En enande algoritm utgör sektionens final. LRTA* infördes av Korf (1990), är den första och mest kända lärande realtid heuristiska sökalgoritm. Den viktigaste idén ligger i att blanda sig i och backa upp heuristiska värden (figur 2). Fem, fem, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, sex, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, tre, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, fem, tre, fem, fem, fem, fem, fem, fem, tre, fem, fem, fem, fem, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, tre, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, fyra, För tydlighetens skull beskriver alla pseudokoder i detta dokument endast en enda rättegång. Särskilt, i det nuvarande tillståndet s, LRTA* med en lookahead av en anser de omedelbara grannarna (linjerna 4-5 i figur 2 ). För varje grannstat, två värden beräknas: utförande kostnaden för att komma dit från den nuvarande staten (härefter betecknas av g) och den beräknade genomförandekostnaden för att komma till den närmaste målstaten från grannstaten (härefter betecknar h). Medan g är känd exakt, h är en heuristisk uppskattning. LRTA* färdas sedan till det tillstånd som har det lägsta f = g + h-värdet (linje 7). Dessutom uppdateras det heuristiska värdet av det nuvarande tillståndet om det lägsta f-värdet är större än det heuristiska värdet av det nuvarande tillståndet (linje 6). 6 LRTA* 1 initiera heuristic: h ← h 0 2 återställa det nuvarande tillståndet: s ← s start 3 medan s Sg gör 4 generera barn en flytta bort från tillstånd s 5 hitta staten s ′ med den lägsta utföra åtgärden för att komma till s ′ 8 slutet medan Korf (1990) visade att i ändliga domäner där måltillståndet kan nås från alla stater och alla åtgärdskostnader är icke-noll, LRTA* finner ett mål på varje försök. Dessutom, om den initiala heuristiska funktionen är tillåtlig kommer LRTA* att konvergera till en optimal lösning efter ett begränsat antal försök. Jämfört med A*-sökning har LRTA* med en lookahead av en betydligt kortare första flytta eftersläpning och hittar suboptimala lösningar mycket snabbare. Konvergera till en optimal (t.ex. lägsta utförandekostnad) lösning kan dock vara dyrt i fråga om antalet försök och den totala genomförandekostnaden. Tabell 1 listar mätningar i genomsnitt över 1000 konvergenskörningar på de fem spelkartorna i sökområdet (detaljer i avsnitt 5.1). Skillnaderna blir mer uttalade för större problem (Figur 3 ). Ishida (1997) hänvisade till sådana felaktigheter i heurismen som "heuristiska depressioner". Han studerade dem för det grundläggande fallet av LRTA* med en lookahead av en. Heuristiska depressioner generaliserades senare för viktade LRTA* och godtyckliga lookahead i (Bulitko, 2004) under namnet γ-fällor. 6. Vad är det som händer? Detta villkor är inte nödvändigt om heurismen är konsekvent som f - värden kommer att vara non-decreasing längs alla lookahead grenar. I allmänhet finns det inget behov av att minska h-värdet i något tillstånd om den initiala heurismen är tillåtlig. I processen att "fylla in" heuristiska depressioner kan agenten ådra sig betydande kostnader för utförande genom att röra sig fram och tillbaka inne i depressionen. Detta sker på grund av att LRTA* med en lookahead av en är myopic och genomför en minsta mängd planering per drag. Om planering är billigare än utförande, då en naturlig lösning är att öka mängden planering per drag med hopp om att eliminera heuristiska lokala minima till en lägre genomförandekostnad. I LRTA* genomförs ytterligare planering per drag genom djupare lookahead-sökning. Den heuristiska uppdaterings- och åtgärdsvalsreglerna som infördes i föregående avsnitt kan utvidgas till ett godtyckligt lookaheaddjup på ett sätt inspirerat av den vanliga mini-max sökningen i spel (Korf, 1990). Korf kallade den nya regeln "mini-min" och konstaterade empiriskt att djupare lookahead minskar kostnaden för utförandet men ökar planeringskostnaden per drag. Fenomenet kan illustreras med ett handspårbart exempel i figur 4. Vart och ett av de sex tillstånden visas som en cirkel med de åtgärder som visas som kanter. Varje åtgärd kostar 1. Den första heuristiska h 0 är tillåtlig men felaktig. Heuristiska värden före och efter den första prövningen visas som tal under varje tillstånd (cirkel). Både LRTA* med en lookahead på en och två konvergera till sin slutliga heuristik i en rättegång. Men det extra ply of lookahead drar nytta av de två extra heuristiska värderingarna och minskar därmed kostnaderna för utförandet från 5 till 3 drag. Å andra sidan ökar planeringskostnaden för varje drag från 2 till 4 noder. I allmänhet, mer planering per åtgärd "kompenserar" för felaktigheter i den heuristiska funktionen och gör att man kan välja bättre rörelser. Tabell 2 visar denna effekt i genomsnitt över de 1000 problemen med att hitta en väg. Minskningen av kostnaderna för utförande på grund av djupare lookahead blir mer uttalad i större problem ( Figur 5). Lookahead-sökning i LRTA*-liknande algoritmer har fått stor uppmärksamhet i litteraturen. Russell och Wefald (1991) och Koenig (2004) analyserade urvalet av lookaheaddjupet optimalt i förhållande till den totala kostnaden (dvs. en viktad kombination av planerings- och genomförandekostnader). Bulitko, Li, Greiner och Levner (2003) och Bulitko (2003) undersökte patologiska fall av djupare lookahead som ökar både kostnader för utförande och planering. Skalbarheten för LRTA* för stora problem bestäms av två av dess attribut. För det första använder den den initiala "optimistiska" heuristiska funktionen för de okända områdena i sökområdet och mer informerade, "realistiska" funktionen för de utforskade områdena. Detta resulterar i den så kallade "optimismen inför osäkerheten" där agenten ivrigt utforskar nya delar av rummet. Konvergenstiden förlängs följaktligen och lösningens kvalitet varierar betydligt under efterföljande försök (Shimbo & Ishida, 2003). För det andra kan den fullständiga konvergensprocessen vara oåtkomlig när det gäller körtid och den mängd minne som krävs för att lagra den heuristiska eftersom man söker optimala lösningar. Faktum är att även enkla problem kan vara svåråtkomliga när det gäller att hitta optimala lösningar (t.ex., den generaliserade glidande kakel pussel av Ratner & Warmuth, 1986). Shimbo och Ishida (2003) föreslog en viktad version av LRTA* som ett systematiskt sätt att ge upp optimala lösningar. Författarna hävdade att optimala lösningar sällan behövs i praktiken, och att de inte heller kan uppnås på stora områden. Följaktligen måste användaren nöja sig med suboptimala men tillfredsställande lösningar. Viktad LRTA* är samma algoritm (LRTA*) kör med en otillåtlig initial heuristic. Otillåtligheten begränsas som för varje tillstånd dess h(s) värde krävs för att vara övre-bounded av (1 +  på)h * (s) där h * (s) är det verkliga avståndet till mål. Den resulterande avvisningsmöjligheten leder till en optimal lösning som en sådan LRTA* konvergerar till. Genom att ge upp optimalitet på ett kontrollerat sätt får algoritmen snabbare konvergens, mindre minneskrav och högre stabilitet. Observera att 0-LRTA* motsvarar den ursprungliga LRTA*. Shimbo och Ishida (2003) använde Manhattan avstånd skalas av (1 +  på) som den första heuristiska h 0. Den underliggande idén kan illustreras i en fem-state domän (Figur 6 ). Till vänster, den första 128 LÄRANDE I REAL-TIME SÖKNING: EN UNIFYING FRAMEWORK heuristic listas omedelbart under de fem staterna (visas som cirklar). Varje åtgärd (visas med en kant) har kostnaden för genomförandet av 1. Varje prövning av LRTA* kommer att innebära fyra drag och kommer att uppdatera de heuristiska värdena. Värdena efter varje försök listas som på varandra följande rader. Efter 16 drag (4 försök) kommer LRTA* att konvergera till den perfekta heurismen. Till höger börjar vi med samma heuristiska multiplicerat med (1+) = 2. Som visat där, 1-LRTA* tar bara en försök (dvs. 4 drag) att konvergera. I allmänhet, genom att skala den initiala (tillåtliga) heuristiska med (1 + på) mängden underskattning av en tillåtlig initial heuristisk i förhållande till den perfekta heuristiska minskas i många stater. Därför minskas antalet uppdateringar (linje 6 i LRTA*, figur 2 ) som behövs för att öka ett tillstånds initiala heuristiska värde till dess slutliga värde. På motsvarande sätt sänks kostnaderna för genomförandekonvergens och lärandet påskyndas. Figur 7 visar korrelationen i sökområdet. Avvikelsen är summan av underskattning i den initiala heuristiska (1 +  på)h 0 i genomsnitt över alla tillstånd på kartan (s  på S): Här- betecknar icke-negativ subtraktion: a-b är lika med a − b om resultatet är positivt och 0 annars. Som vanligt är h * den perfekta heuristiska och h 0 är oktilavståndet. Heuristikerna tas med avseende på 1000 slumpmässiga måltillstånd (s mål ) definieras i avsnitt 5.1. På den negativa sidan är skalningen enhetlig över alla stater och kommer ibland att resultera i att de skalade värdena överskrider de perfekta heuristiska värdena. Sådan otillåtlighet kan leda till suboptimala lösningar 129 BULITKO & LEE som illustreras i figur 8. Specifikt är den initiala heurismen tillåtlig (värdena för de fem staterna visas ovanför cirklarna i den vänstra delen av figuren). Alla åtgärder (visas som pilar) har kostnaden för genomförandet av 1. Således konvergerar LRTA* till den optimala vägen (dvs. genom topptillståndet). Å andra sidan, skalning heuristic med (1 +  på) = 3 (visas till höger) leder 2-LRTA* att konvergera på en längre suboptimal väg (genom de nedre två staterna). Sammanfattningsvis tenderar skalning av en inledande (tillåten) heuristisk med 1 +  på att minska heurismens underskattningsfel och därmed påskynda konvergensen. Allteftersom den viktade heurismen gradvis blir mer överskattande, ökar de slutliga lösningarnas suboptimalitet, och så småningom minskar den totala konvergensen (på grund av mindre informativ viktad heuristisk). Tabell 3 visar trenderna inom området för att hitta vägar. Återigen, effekten är mer uttalad för större problem (Figur 9 ). Observera att en liknande effekt har observerats med viktad A* sökning där en vikt w sätts på den heuristiska h. När w överstiger 1, är färre noder expanderas på bekostnad av suboptimala lösningar (Korf, 1993). Tabell 4 visar resultaten av körvägd A* om de problem som används i tabell 3.  Både LRTA* och LRTA* lär sig genom att uppdatera sin heuristiska funktion medan de avancerar i statsrymden. SLA* (Shue & Zamani, 1993) införde en backtrackingmekanism. Det vill säga, när agenten gör en uppdatering till det heuristiska värdet av den nuvarande staten, går han tillbaka till sitt tidigare tillstånd. Detta ger agenten två möjligheter: i) att uppdatera det heuristiska värdet av det tidigare tillståndet och ii) eventuellt välja en annan åtgärd i det tidigare tillståndet. Ett alternativt system skulle vara att uppdatera 130 LÄRANDE I REAL-TIME SÖKNING: EN UNIFYING FRAMEWORK Den underliggande intuitionen kan illustreras med ett enkelt exempel i Figur 10. Ännu en gång, tänk på en endimensionell femstatsdomän. Varje åtgärd har en genomförandekostnad på en. Den initiala heurismen är korrekt i de två vänstra staterna och en lägre i de tre högra staterna. Vid varje rättegång kommer LRTA* att höja ett enda tillstånds heuristiska värde. Därför behövs tre prövningar (12 drag) för att göra den heuristiska fullkomlig. SLA*, å andra sidan, kommer till mellantillståndet i 2 drag, uppdaterar sitt värde från 1 till 2, bakspår till det andra tillståndet från höger, ökar sitt värde från 2 till 3, bakspår till höger mest tillstånd, och ökar sitt värde från 3 till 4. Agenten kommer sedan att ta 4 steg mot målet, efter den nu perfekta heuristiska. Som ett resultat, den första prövningen är längre (8 vs 4 drag) men det totala antalet rörelser tills konvergensen minskas (från 12 till 8). Den SLA* algoritmen är nästan identisk med LRTA* med en lookahead av en (Figur 2 ). Den enda skillnaden är att när man höjer statsvärdet i linje 6 vidtar agenten en åtgärd som leder till dess 131 BULITKO & LEE tidigare tillstånd och inte staten s ′ som i linje 7 av LRTA*. Om det tidigare tillståndet inte existerar (dvs algoritmen nådde starttillståndet) vidtas inga åtgärder, men det heuristiska värdet är fortfarande uppdaterat. SLA * backtracks varje gång dess heuristic uppdateras (dvs., lärande ägde rum). Detta orsakar mycket betydande kostnader för genomförandet av den första rättegången. Faktum är att allt lärande sker under den första rättegången, vilket vi kommer att bevisa i Theorem 7,8. Vid större problem kan användaren vilja ha en suboptimal lösning innan konvergensprocessen slutförs. För att ta itu med detta problem, SLA*T, infördes i (Shue, Li, & Zamani, 2001), ger användaren kontroll över mängden lärande som ska göras per försök. Nämligen, SLA*T backtracks först efter det att det uttömmer en användarspecificerad inlärningskvot. Det finns två primära effekter av bakåtspårning på de mätvärden som vi anser i detta dokument. För det första minskar större värden på inlärningskvoter kostnaderna för genomförandet av varje försök eftersom mindre bakåtsträvande sker. I ytterligheten kan inlärningskvoten sättas i oändlighet, vilket omvandlar SLA*T till backtracking-free LRTA* med en lookahead av en. I andra änden av spektrumet (med en inlärningskvot på noll) backar SLA*T alltid tillbaka när man uppdaterar ett heuristiskt värde och blir likvärdigt med SLA*. Mer bakåtsträvande tenderar att påskynda konvergensprocessen (dvs. minska kostnaderna för att genomföra konvergensen) eftersom färre försök behövs för att konvergera (återkalla exemplet i figur 10 ). Empiriskt sett är den första effekten av backtracking tydligast i 8-pussel (Tabell 5) samt sökvägen uppgift med små kartor (Tabell 6 ). Det är fortfarande en öppen fråga varför trenden inte observeras i fråga om större uppgifter (tabell 7). Den andra effekten av backtracking är att mängden minne som krävs för att lagra de lärda heuristiska värdena minskar. 7 Under backtracking, agenten tenderar att uppdatera heuristiska värden i tidigare besökta stater. Sådana uppdateringar kräver inte att ytterligare minne allokeras. Den minnesbesparande effekten ses i alla problemstorlekar i tabell 5 och tabell 7. De föregående avsnitten införde tre förlängningar av basalgoritmen LRTA*. Tabell 8 Bulitko, 2004), som också använde en heuristisk viktparameter γ = 1/(1 +  på) till samma effekt som viktad LRTA*. Dessutom använde γ-Trap en mer aggressiv heuristisk uppdateringsregel, betecknad som "max min" i tabellen, och använde heuristiska värden i alla stater (i motsats till gränsen för lookahead sökning endast). I stället för att vidta en enda åtgärd mellan lookahead sökning episoder, det tillämpade d åtgärder för att amortera planeringskostnaden. Vi kommer nu att kombinera de tre förlängningarna till en enda algoritm som kallas Learning Real-Time Search eller LRTS. Det visas i den sista raden i tabellen och, på ett förenklat sätt, i figur 11. Den detaljerade pseudo-kod som krävs för att återinföra algoritmen samt för att följa teoremet bevis finns i figur 20, Bilaga A. Vi kommer nu att gå igenom driften av LRTS och förklara kontrollparametrarna. I linje 1, försök initieras genom att ställa in nuvarande tillstånd s av agenten till starttillståndet s start och återställa den mängd lärande som gjorts på prövningen (u). Så länge målet inte nås lämnar LRTS-agenten planering (linjerna 3 och 4), lärande (linje 5) och genomförande (linjerna 6-11). Under planeringstillståndet använder LRTS modellen för sin miljö (oförklarligt uppdaterad när nya tillstånd kommer in i agentens synradie) för att generera alla barntillstånd i det nuvarande tillståndet upp till d flyttar bort. På varje lookahead nivå (i = 1, 2,.., d), LRTS finner den mest lovande tillstånd (s i ) som minimerar den viktade uppskattningen av det totala avståndet: Den lookahead sökning som utförs i linje 5 har komplexiteten i O (b d ) om inget barn tillstånd uppnås mer än en gång och b är grenningsfaktorn. På kartor minskas dock komplexiteten mycket till O(d n ) där n är kartans dimensionalitet. Således, i både vägplanering och sensornätverk routing uppgift, lookahead har en komplexitet av O(d 2 ). Liksom γ-Trap använder LRTS den så kallade "max min" heuristisk uppdatering (eller inlärning) regel i linje 5. Om den initiala heurismen är tillåtlig, vill agenten öka den så aggressivt som möjligt samtidigt som den är tillåtlig. Lemma 7.1 kommer att visa att sätta det heuristiska värdet h av det nuvarande tillståndet s till det maximala av minima som finns på varje ply bevarar tillåtligheten av h hela tiden. I rad 6 läggs sedan mängden ökning till det heuristiska värdet av det nuvarande tillståndet (h(s)) till den kumulativa mängden lärande som hittills gjorts på försök (u). Om den nya mängden lärande inte överskrider inlärningskvoten T kommer agenten att utföra d flyttar till den mest lovande gränsstaten s d sett under lookahead (linje 8). Flyttarna läggs till i stigen så att de kan vara "undna" senare under backtracking. Om den nya mängden lärande överstiger inlärningskvoten T kommer agenten att backa tillbaka till sitt tidigare tillstånd (linje 10). Genom att göra det kommer det att "undanröja" de sista åtgärderna. De sista d-åtgärderna är sålunda avlägsnade från den väg som hittills rests under rättegången. Observera att backtracking åtgärder räknas i kostnaden för utförande. Vi uppmuntrar nu läsaren att se över de handspårbara exemplen i avsnitten 6.2, 6.3 och 6.4 eftersom de visar LRTS-drift inom enkla domäner. I viktningsexemplet (avsnitt 6.3) bör γ sättas till 1/(1+) för att göra det möjligt för LRTS att bete sig som  med-LRTA*. Detta avslutar presentationen av LRTS algoritm och vi kommer nu att lyfta fram dess egenskaper med teoretiska och empiriska resultat. LÄRANDE I REAL-TIME SÖKNING: EN UNIFYING RAM RAMEN för LRTS omfattar LRTA*, viktad LRTA*, SLA* och γ-Trap som specialfall (tabell 8). Detta faktum presenteras formellt i följande teorem. Alla bevis finns i bilaga B. Observera att även om följande antaganden inte är obligatoriska för sökning i realtid, behövs de för bevisen. Särskilt antas sökytan vara deterministisk och stationär. Dessutom påverkas agentens nuvarande tillstånd endast av agentens handlingar. Slutligen har agenten tillräcklig kunskap om miljön för att genomföra en lokal sökning (dvs. lookahead) av djup d i sitt nuvarande tillstånd. Teorem 7.1 LRTS(d = 1, γ = 1, T = ∞) motsvarar LRTA* med en lookahead av en. Tidigare har konvergens och fullständighet bevisats för specialfallen LRTA*, LRTA* och SLA*. Vi kommer nu att bevisa dessa egenskaper för alla giltiga värden av lookahead d  på N, d ≥ 1, den heuristiska vikten γ  på R, γ på 0, 1] och inlärningskvoten T på R på {∞}, T på 0. Definition 7.1 Ett slipsbrytande system används när två eller flera stater har samma f = g + h-värden. Bland kandidatstater med lika mycket f - värden väljer slumpmässiga slipsbrytande en slumpmässigt. Detta system användes i (Shimbo & Ishida, 2003). Systematiskt slipsbrytande används av Furcy och Koenig (2000) använder en fast åtgärd beställning per nuvarande tillstånd. Beställningarna genereras dock slumpmässigt för varje sökproblem. Slutligen, fast slips-brytning använder alltid samma åtgärd beställning. Vi använder det senare systemet för alla våra experiment eftersom det är det enklaste. Lemma 7.1 (Antagande) För alla giltiga T, γ, d och en tillåtlig initial heuristisk h 0, hålls den heuristiska funktionen h tillåten hela tiden under LRTS (d, γ, T ) sökning. En icke-trivial övre gräns på h * (s 0 ) + T γ kan åläggas den lösning som LRTS framställde i den första studien. Detta kräver dock en mindre utvidgning av LRTS-algoritmen. Således listar vi förlängningen och teorem i figur 21, Bilaga A och Theorem B.1, Bilaga B respektive. Teorem 7.8 (en försökskonvergens) För alla giltiga γ, d och en tillåtlig initial heuristisk h 0, är den andra prövningen av LRTS(T = 0) med systematiska eller fasta slipsbrytningar garanterad att vara slutlig. På så sätt sker all inlärning och utforskning under den första rättegången. Vi har infört en treparametersalgoritm som förenar flera tidigare föreslagna förlängningar till basen LRTA*. Vi har också teoretiskt och empiriskt visat påverkan av varje parameter oberoende av de andra två parametrarna i avsnitten 6.2, 6.3 och 6.4. Sammanfattningen av influenserna finns i tabell 9. En upppil/nerpil innebär en ökning/minskning av mätvärdet. Notation a → p → b indikerar att parametern p ökar från a till b. För att illustrera: ↓ i skärningspunkten mellan raden som heter "konvergensutförandekostnad" och kolumnen som heter "1 → d → ❌" anger att konvergensutförandekostnaden minskar när d går upp. Tabell 9 : Sammanfattning av påverkan av LRTS-parametrar inom sökområdet. I det här avsnittet tar vi hänsyn till effekterna av parameterkombinationer. Figur 12 visar effekten av lookahead djup d som en funktion av den heuristiska vikt γ och inlärningskvoten T. Särskilt, för varje värde av γ och T, den vänstra tomten visar skillnaden mellan konvergens genomförandekostnader för lookahead värden av d = 1 och d = 10: Ljusare nyanser indikerar högre effekt av att öka d från 1 till 10. På samma sätt visar rätt diagram hur d påverkar det minne som krävs för konvergens. Ljusare nyanser indikerar 136 LÄRANDE I REAL-TIME SÖKNING: EN UNIFYING FRAMEWORK starkare effekt av d (dvs större skillnader). Varje punkt är i genomsnitt över de 1000 konvergenskörningarna inom området för att hitta vägar. Vi observerar att större värden av inlärningskvot och högre värden av heuristisk vikt förstorar minskningen av minnet på grund av ökande lookahead djup. Observera att tomten inte visar minneskraven för olika värden av γ och T utan snarare minskningen av minneskraven när d ökar från 1 till 10. Figur 13 visar inverkan av γ som en funktion av d och T under samma förhållanden. Inlärningskvoten tycks inte påverka effekten av γ på den slutliga lösningens suboptimalitet. En djupare blick gör dock γ mindre effektivt i detta avseende. Vi tror att det beror på att djupare lookahead kompenserar för fler felaktigheter i den heuristiska funktionen. Därför gör viktningen av heurismen med γ mindre skillnad. Figur 14 visar T:s inverkan som en funktion av d och γ på samma 1000-tal problem med att hitta vägar. Att minska inlärningskvoten T från 500 till 0 leder till en ökad eftersläpning. Som diskuterats tidigare, mer backtracking tenderar att spara minne och påskynda konvergens. Siffran visar både trender och visar att d och γ påverkar effekterna av backtracking. Den vänstra handlingen visar att mer bakåtsträvande är mest effektivt för att påskynda konvergensen för lägre heuristiska vikter (γ = 0,1). Tvärtom visar rätt diagram att högre heuristiska vikter (nära γ = 1) gör backtracking mest effektivt för att minska det minne som krävs för konvergens.  Sammantaget är influenserna icke-triviala och, enligt våra experiment, domänspecifika. Även om vissa lätt kan förklaras, andra verkar vara ett resultat av samspelet mellan de tre parametrarna med strukturen av problemet utrymme. Följaktligen är valet av optimala parametrar för ett specifikt prestandamått och en konkret domän för närvarande en fråga om försök och fel. Medan manuell inställning av kontrollparametrar är ett typiskt scenario inom artificiell intelligens, framtida forskning kommer att undersöka automatisk parameterjustering. I detta avsnitt listar vi parameterkombinationer som optimerar var och en av prestationsmåtten och förklarar den underliggande logiken. De bästa kombinationerna av parametrar söks i följande parameter utrymme: lookahead d  till {1, 2,.., 10}, heuristisk vikt γ  till {0.1, 0.2,..., 1.0}, och inlärningskvoten T  till {0, 5, 10, 50, 100, 500, 1000, 5000, 10000, ∞}. För var och en av de tusen kombinationerna av parametrarna körde vi LRTS tills konvergens på testsviten med 1000 sökproblem som beskrivs i avsnitt 5.1. Resultaten visas i tabell 10 och förklaras nedan. Konvergenskostnaden för genomförandet är lägst när kvaliteten på de enskilda rörelserna är den högsta. På så sätt gynnas en djupare blick som leder till mer planering per drag. Höga värden av γ är oönskade eftersom LRTS söker nära optimala lösningar och tar längre tid att konvergera. Mycket låga värden av γ är också oönskade som den viktade initial heuristic blir mindre och mindre informativ (Tabell 3). Det bästa värdet ligger därför någonstans i mitten (0.3). Slutligen, ingen backtracking föredras eftersom då konvergens är den snabbaste på de större kartor som används i detta experiment (Tabell 7). Konvergenskostnader för planering definieras som den totala planeringskostnaden för alla åtgärder tills konvergens uppnås. Djupare lookahead leder till snabbare konvergens men fyrfaldigt ökar planeringskostnaden för varje drag (se avsnitt 6.5). På det hela taget är därför ytlig lookahead att föredra. Detta förklarar också den optimala parameterkombinationen för att minimera planeringskostnaden per drag som i LRTS endast beror på d. Sammanlagda konvergenskostnader. Här minimerar vi en viktad summa av planerings- och genomförandekostnaderna. Detta är ett gemensamt mål som tidigare studerats i (Russell & Wefald, 1991; Koenig, 2004). Vi antar de senares inställningar och tar med de två mätvärdena (exekveringskostnaden och planeringskostnaden) till en enda skalar som uttrycks i antalet stater. Nämligen definieras vår totala konvergenskostnad som kostnaden för att genomföra konvergensen multiplicerad med planeringshastigheten plus den totala planeringskostnaden (avsnitt 4). Till exempel, om agenten konvergerade i 1000 enheter av utförande kostnader, anses vara totalt 5000 stater under planering (dvs. i genomsnitt fem stater per enhet för utförande kostnad), och planeringshastigheten är 200 (dvs. 200 stater kan beaktas vid planering medan en enhet för resor utförs), då den totala konvergenskostnaden är 1000×200+5000 = 205000, tydligt domineras av 138 LÄRANDE I REAL-TIME SÖKNING: EN UNIFIYING RAMVERK genomförandekomponent. Mer planering per drag tenderar att minska kostnaderna för att genomföra konvergensen och är därför att föredra när planeringshastigheten är hög (dvs. planering är billig i förhållande till genomförandet och genomförandekostnaden dominerar den totala kostnaden). Omvänt är mindre planering per drag att föredra när planeringshastigheten är låg. Både Russell och Wefald (1991) och Koenig (2004) använde detta resonemang för att välja det optimala lookaheaddjupet i sina LRTA*-baserade realtidssökningsalgoritmer. Inom området för att hitta vägar är de bästa värdena för γ och T för snabbaste konvergens 0,3 och ∞ som diskuteras ovan. Det bästa värdet av lookahead beror på planeringshastigheten: djupare lookahead (10 vs. 1) föredras när planeringshastigheten är tillräckligt hög och mer planering per drag kan ges. Suboptimalitet är noll med γ = 1 oavsett d och T. Minnet. Den optimala parameterkombinationen (10, 0.3, 0) överensstämmer med den tidigare analysen: mer bakåtspårning (T = 0) minskar minnesförbrukningen, lägre heuristisk vikt γ leder till mindre prospektering (eftersom LRTS är nöjd med suboptimala lösningar), och eftersom heuristiska värden lagras d åtgärder isär, är högre lookahead föredras. Genom att justera LRTS-kontrollparametrarna kan agenten uppnå konvergens där det tidigare varit omöjligt på grund av minnesbegränsningar. I följande, vi antar inställningarna för Shimbo och Ishida (2003) och Bulitko (2004) och överväga hundra 15-pussel först publiceras av Korf (1985). Det är känt att FALCONS och LRTA* med en lookahead av en inte kan konvergera till optimala lösningar på något av de 100 pussel med minne begränsat till 40 miljoner stater (Shimbo & Ishida, 2003). Å andra sidan kan konvergens till suboptimala lösningar uppnås med båda Vi gör uppgiften mer utmanande genom att sänka minnesgränsen tio gånger från fyrtio till fyra miljoner stater. Medan vi inte kunde hitta en uppsättning d, T, γ parametrar som tillät LRTS att konvergera till optimala lösningar på alla 100 fall, algoritmen gjorde konvergera till lösningar som i genomsnitt var bara 4% sämre än optimal på alla 100 pussel (Tabell 11). Lägre värden för T och högre värden för d ökar minneskostnadseffektiviteten och gör det möjligt att öka γ vilket leder till lösningar av högre kvalitet. Sammanfattningsvis påverkar justeringen av kontrollparametrarna för LRTS signifikant dess prestanda. Vår analys av den individuella och kombinerade påverkan av parametrarna på flera praktiskt relevanta prestandamått ger en utövare en bättre intuition för tillämpningsspecifik parameterinställning. Kanske viktigare, det öppnar en intressant linje av forskning om automatiskt urval av optimala parametrar på grundval av effektivt mätbara egenskaper hos en domän och målprestanda metrisk. BULITKO & LEE En andra tillämpning av LRTS övervägas är routing i ad hoc trådlösa sensornätverk. Sensornoder har i allmänhet begränsad beräkningskraft och energi, vilket gör att enkla, energieffektiva routingrutiner vanligtvis används inom sensornätverk. Olika tillämpningar finns, inklusive militära (Shang et al., 2003), miljöövervakning (Braginsky & Estrin, 2002) och spaningsuppdrag (Yan, He, & Stankovic, 2003). Som sådan, routing i sensornätverk är av intresse för en stor gemenskap av användare. Den distans Vector Routing (DVR) algoritm används ofta i nätverk routing (Royer & Toh, 1999). I synnerhet används DVR inom ramen för gränsgatewayprotokollet som används för att styra trafiken över hela Internet. I DVR bibehåller varje nätverksnod en heuristisk uppskattning av avståndet till destinationen/målnoden. Vi observerar att DVR är konceptuellt mycket lik LRTA* med en lookahead av en. Således, tillämpa LRTS i nätverket routing domän är i huvudsak likvärdigt med att utöka DVR med den heuristiska vikt γ och bakåttracking mekanism kontrolleras av inlärningskvoten T. Observera att det inte finns någon analog av djupare lookahead i DVR eftersom varje nätverk nod inte lär sig en explicit modell av nätverket och, följaktligen, inte är medveten om några nätverksnoder utanför dess omedelbara grannar. Därför är d begränsad till en. För att visa effekten av de två DVR-tilläggen valde vi den installation som användes i en ny tillämpning av realtids heuristisk sökning på nätverksrouting (Shang et al., 2003). Specifikt, nätverkssensorn noder antas släppas från himlen för att övervaka territorium, landning i en slumpmässig spridning, och därmed nödvändig ad hoc routing för att möjliggöra dataöverföringar. Vi anser att det rör sig om en fast destination för varje sändning, som simulerar varje källnod som tillhandahåller information till ett centralt informationsnav (t.ex. en satellitupplänk). Observera att LRTA* i sökområdet har tillgång till sina grannars heuristiska värden utan extra kostnad eftersom alla heuristiska värden lagras i centraliserat minne. Detta är inte fallet i ad hoc-nät, där varje nod bibehåller en uppskattning av antalet humle till målnoden (h heuristic). En naiv tillämpning av LRTA* skulle fråga grannnoder för att hämta sina h-värden. Detta skulle dock avsevärt öka nättrafiken, vilket skulle leda till en snabbare utarmning av nodernas energikällor och göra nätet lättare att upptäcka. Vi antog standardlösningen där varje nod inte bara lagrar sitt eget heuristiska värde utan också sina närmaste grannars senast kända heuristiska värden. När sedan en nod uppdaterar sitt eget heuristiska värde, meddelar den alla sina grannar om förändringen genom att sända ett kort kontrollmeddelande. Den sista stora skillnaden från sökvägen är att noderna inte vet vare sig deras geografiska läge eller koordinaterna för destination noden. Således är det euklidiska avståndet inte tillgängligt och den initiala heuristiska initieras till en för alla noder utom destination noden där det är satt till noll. I de experiment som redovisas nedan fördelas N-sensornoderna slumpmässigt på ett tvådimensionellt X × Y-rutnät så att inga två noder upptar samma plats. Varje nod har en fast sändningsradie som bestämmer antalet grannar en nod kan sända meddelanden till (och vars heuristiska värden den måste lagra). För att ange en enda problem instans, är distinkt start (källa) nod och mål (destination eller nav) noder slumpmässigt utvalda från N noderna. Startnoden måste skicka ett datameddelande till målnoden. Genom att göra det kan det skicka ett meddelande till en av sina grannar som sedan kommer att åter sända meddelandet till en annan nod, etc. Varje överföring mellan två angränsande noder ådrar sig en genomförandekostnad på ett hopp. När meddelandet når destinationen / mål noden, en ny rättegång börjar med samma start och mål noder. Konvergens uppstår när inga heuristiska värden uppdateras under rättegången. Målet är att hitta en kortaste väg från startnoden till målnoden genom att lära sig bättre heuristiska värden över upprepade försök. Vi tar mätningar av fyra mätvärden parallellt med dem som används inom området för vägsökning: konvergens genomförandekostnad är det totala antalet humle som transporteras med meddelanden under konvergens; första försök genomförande kostnaden är antalet humle reste på den första rättegången; suboptimalitet av den slutliga lösningen är överskottet av genomförandekostnaden för den slutliga rättegången på kortast möjliga väg. Om till exempel nätet konvergerar till en rutt på 120 humle, medan den kortaste sträckan är 100 humle, är suboptimaliteten 20 %. Konvergenstrafiken definieras som den totala informationsvolym som överförs genom nätet under konvergensen. Varje datameddelande räknas som ett. Korta styrmeddelanden (används för att meddela nodens grannar om en uppdatering till nodens heuristiska funktion) räknas som en tredjedel. Interferens är inte modellerat i denna simulering. Vi antar att schemaläggning utförs oberoende av routing strategi, och att olika scheman inte kommer att allvarligt påverka prestanda routing algoritmer. Observera att eftersom sändningsfördröjning och tidpunkter inte är modellerade, skulle det vara svårt att modellera störningar på ett korrekt sätt. Fyra omgångar nätverk med 50, 200, 400 och 800 noder vardera övervägdes. Noderna placerades slumpmässigt på ett fyrkantigt rutnät med dimensionerna 20 × 20, 30 × 30, 50 × 50 respektive 80 × 80. Varje sats bestod av 100 slumpmässigt genererade nätverk. För varje nätverk utfördes 25 konvergenskörningar med parametervärdena γ = {0.1, 0.3, 0,5, 0,7, 1} och T = {0, 10, 100, 1000, 100000}. I det följande presenterar vi resultaten från satsen 800-node nätverk. Samma tendenser observerades även i mindre nät. Vi börjar med att visa inflytandet av de två kontrollparametrarna isolerat. Tabell 12 visar inverkan av den heuristiska vikten γ utan backtracking. Som förväntat påskyndar mindre värden av γ konvergensen men ökar den slutliga lösningens suboptimalitet. Dessa resultat motsvarar de som rapporteras i tabell 3 för sökområdet. Tabell 13 visar hur inlärningskvoten T påverkar när den heuristiska vikten γ är satt till en. Mindre värden av T ökar mängden backtracking och påskyndar konvergenskostnaden men förlänger den första prövningen. Detta motsvarar resultaten i 8-pussel (Tabell 5) samt i sökvägar med små kartor (Tabell 6 ). Vi kommer nu att överväga effekten av parameterkombination. Det fasta lookaheaddjupet av en gör det tvådimensionella parameterutrymmet lättare att visualisera på konturytor. I stället för att plotta effekten av en parameter på ett mätvärde som en funktion av de andra två kontrollparametrarna, kommer vi 141 BULITKO & LEE nu att rita själva mätvärdet. Figur 15 visar den första försök och konvergens genomförandekostnader för alla kombinationer av γ och T. Ljusare områden indikerar högre kostnader. Figur 16 visar den slutliga lösningens suboptimalitet och den totala trafiken på en konvergenskörning, i genomsnitt över 100 nät med 800 noder vardera. Återigen visar ljusare områden högre värden. Sammanfattningsvis kan man, genom att utvidga DVR-algoritmen med den heuristiska vikten och bakspårsmekanismerna för LRTS, minska kostnaderna för att genomföra konvergensen och den totala nättrafiken. Som ett resultat av detta hittas nästan optimala vägar snabbare, med en lägre energiförbrukning. Detta lovande resultat väcker flera frågor för ytterligare forskning. För det första, hur kommer ytterligare routing begränsningar, såsom de som undersökts i (Shang et al., 2003), påverka prestanda för LRTS? För det andra, hur kommer fördelarna med LRTS skala för fallet med flera meddelanden med samma destina-142 LÄRANDE I REAL-TIME SÖKNING: EN UNIFYING RAM SOM passerar genom nätverket samtidigt? Den senare frågan gäller också vägplanering med flera minnesdelningsenheter som är en vanlig situation i gruppbaserade spel. I det här dokumentet övervägde vi samtidiga planerings- och inlärningsproblem såsom realtidssök i till en början okända miljöer samt routing i ad hoc trådlösa sensornätverk. Inlärning i realtid sökmetoder plan genom att genomföra en begränsad lokal sökning och lära genom att upprätthålla och förfina en statsbaserad heuristisk funktion. Således kan de reagera snabbt på användarens kommandon och ändå konvergera till bättre lösningar över upprepade erfarenheter. Vi analyserade tre kompletterande förlängningar av basen LRTA* algoritm och visade deras effekter med hand-spårbara exempel, teoretiska gränser, och omfattande empirisk utvärdering inom två olika områden. Vi föreslog sedan en enkel algoritm, kallad LRTS, som förenade förlängningarna och studerade problemet med att välja optimala parameterkombinationer. I det nuvarande och framtida arbetet ingår att utvidga LRTS med automatiserade system för rymduttag, metoder för att approximera funktioner för heuristiska och automatiserade parameterurvalsmetoder. Det kommer också att vara av intresse att undersöka konvergensprocessen för ett team av LRTS-baserade agenter med delat minne och utöka LRTS för rörliga mål och stokastiska/dynamiska miljöer i videospel, robotik och nätverk.
Dessa förlängningar ingår alla inom ramen för LRTS Ref.
Learning in Real-Time Search: A Unifying Framework
{'venue': 'Journal Of Artificial Intelligence Research, Volume 25, pages 119-157, 2006', 'journal': None, 'mag_field_of_study': ['Computer Science']}