Standardalgoritmer för att hitta den korta est vägen i en graf kräver att kostnaden för en väg är additiv i kant kostnader, och normalt antar att kostnaderna är determinis tic. Vi betraktar problemet med osäkra kantkostnader, med potentiella probabilistiska dependenser bland kostnaderna. Även om dessa beroenden bryter mot standard dynamisk programmering nedbrytning, identifierar vi en svagare stokastisk konsistens villkor som rättfärdigar en generaliserad dynamisk programmering metod baserad på stokastisk dominans. Vi presenterar en reviderad vägplaneringsalgoritm och visar att den producerar optimala vägar under tidsberoende osäkra kostnader. Vi testar algoritmen genom att tillämpa den på en modell av stokastiska bussnätverk, och presentera em pirical prestanda resultat som jämför den med vissa alternativ. Slutligen anser vi att dessa begrepp är spända för en mer allmän klass av problem i den heuristiska sökandet under ovisshet. Merparten av forskningen om stats- och rymdforskningen i Artificial In telligence and Operations Research förutsätter att kostnaden för en väg är summan av kostnaden för dess kanter, och att kostnaden för kanterna är känd med säkerhet. Standardsökalgoritmerna (bästa första (prioriterad-fi rst) sökning, A*) är beroende av dessa antaganden för sina optimalitetsgarantier. Ickelinjära vägkostnader, eller lika, probabilistiska och beroende vägkostnader, kan besegra dessa algoritmer, som vi ser nedan. I detta dokument fokuserar vi på problemet med proba bilistic och beroende väg kostnader. Vi visar att med tanke på en relativt svag form av stokastisk konsis tens (monotonicitet) tillstånd, något modifierade versioner av standardalgoritmerna kommer att ge optimala resultat. Ändringen är att istället för att lagra bara den bästa vägen till varje mellanliggande nod, lagrar vi nu alla tillåtna vägar, där tillåtlighet baseras på stokastisk dominans. Även om detta kan öka komplexiteten avsevärt, eftersom vi beskär de domi nerade vägarna, är den typiska sökningen långt ifrån exhaustive. I följande avsnitt definierar vi problemet och presenterar ett exempel som illustrerar svårigheten med att använda standardalgoritmerna för planläggning av vägar. Subse quent avsnitt introducerar begreppet stokastisk konsistens, utveckla den modifierade algoritmen, och etablera sina optimala egenskaper. Vi illustrerar sedan algoritmen genom att applicera den på en stokastisk buss-nätverksmodell, och presentera några empiriska resultat på slumpmässigt genererade exempel. Slutligen diskuterar vi en utvidgad tillämpning av de grundläggande begrepp som införts. Överväg ett transportnät med V noder som anger platser och E-kanter som anger möjliga transporteringsåtgärder mellan de platser som är anslutna. Om restiden är statisk (dvs. längden på en resa från a till b beror inte på avgångstiden), då kan vi beräkna den snabbaste rutten från ett givet ursprung till alla möjliga destinationer med hjälp av Dijkstras välkända kortaste-stig algoritm, där kostnaderna på varje länk är restider. Denna algoritm har en värsta-fall komplexitet av O(V2).1 Grundidén bakom denna algo ritm är dynamisk programmering-vi börjar från ori gin och systematiskt hitta de bästa vägarna till alla andra noder, med hjälp av de tidigare hittade bästa vägar. Detta förfarande utnyttjar principen om optimalitet, som föreskriver att den bästa vägen från a till b genom c måste bestå av de bästa vägarna från a till c och c till b. Om restiderna är stokastiska men oberoende (dvs. fördelningen av restider för en länk beror inte på den faktiska restiden på andra), då rutten med den snabbaste förväntade totala restiden kan 1 För glesa grafer, en enkel variant av algoritmen har en körtid av O(Elog V).
REF undersöker ruttplanering under tidsberoende kostnader för gränstrafik.
Path Planning under Time-Dependent Uncertainty
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}