I detta dokument föreslås en distribuerad lösningsmetod för en viss klass av dynamiska resursfördelningsproblem och en dynamisk programplaneringsbaserad mekanism för beslutsfattande, lärande och kommunikation. I den klass av dynamiska resursfördelningsproblem vi anser, måste en uppsättning återanvändbara resurser av olika typer tilldelas uppgifter som anländer slumpmässigt över tid. Tilldelningen av en resurs till en uppgift tar bort uppgiften från systemet, ändrar resursens tillstånd och genererar ett bidrag. Vi bygger upp ett beslutssystem där beslut om resurser i olika grupper av stater fattas av olika aktörer. Vi förklarar hur man samordnar åtgärder av olika agenter med hjälp av ickelinjära funktionella approximationer, och visar att i en distribuerad inställning, ickelinjär approximationer producerar sekvenser av min-kostnads nätverksflöde problem som naturligt ger heltal lösningar. Vi jämför också experimentellt resultaten av de centraliserade och distribuerade lösningsstrategierna. M onolitiska lösningar för optimeringsproblem som uppstår i samband med komplexa system är i allmänhet inte genomförbara. Distribuerad lösningsteknik delar upp dessa problem i löst kopplade underproblem och löser dem självständigt med hjälp av en kommunikationsmekanism mellan underproblem som säkerställer att de oberoende lösningarna av underproblemen ger en lösning av hög kvalitet. I detta dokument presenterar vi en distribuerad lösningsmetod för dynamiska resursfördelningsproblem. Vårt tillvägagångssätt delar upp problemet i subproblem och förlitar sig på flera agenter för att lösa dem. Vi utvecklar en dynamisk programmeringsbaserad kommunikationsmekanism som hjälper varje agent att uppskatta hur deras lösningar påverkar de andra agenterna. Centralt för vårt tillvägagångssätt är användningen av ickelinjära funktionella approximationer för att hantera koordinationen. Dynamiska resursfördelningsproblem som beaktas i detta dokument innebär tilldelning av en uppsättning diskreta och återanvändbara resurser till uppgifter som inträffar slumpmässigt över tid. Varje resurs i systemet har ett tillstånd och en typ som är kopplad till det, som tillsammans bestämmer bidraget av att tilldela en resurs till en uppgift. Ankomstprocessen för uppgifterna är känd endast genom en sannolikhetsfördelning. Tilldelningen av en resurs till en uppgift ger en belöning, tar bort uppgiften från systemet och ändrar resursens tillstånd. Sådana problem uppstår på många områden, såsom dynamisk besättningsplanering (personal är resurser, flygningar är arbetsuppgifter, plats och timmar i tjänst för den anställde är resursstat), flottförvaltning (fordon är resurser, laster är uppgifterna, fordonets plats är resurs tillstånd), maskintilldelning (maskiner är resurser, jobb är uppgifter, maskin slitage är resurs tillstånd), och nödutrustning / personalförvaltning (ambulanser / läkare är resurser, patienter är uppgifter, plats / timmar i tjänst är resurs tillstånd). Flera resursstater och odelbarheten av resurserna skiljer vår problemklass från andra resursfördelningsproblem där en enda delbar resurs (t.ex. datorkapacitet) måste fördelas mellan olika uppgifter. Den senare typen av problem förekommer ofta i distribuerade datorsystem (se Kurose och Simha 1989, Waldspurger et al. Domstolen har beslutat följande dom: Vi ställdes inför detta problem i samband med förvaltningen av fordonsflottor för att betjäna laster som uppstår över tid på en uppsättning platser. I den verkliga verksamheten finns vanligtvis en beslutsagent för varje plats som ansvarar för att hantera fordonen på den platsen, och när den fattar sina beslut ägnar den mycket lite uppmärksamhet åt vad som händer på andra platser. Vi utformar ett effektivt sätt att bedöma effekterna av de beslut som fattas på en viss plats på de beslut som fattas på andra platser och i framtiden. På så sätt kan beslutsfattarna på olika platser arbeta kollektivt för att uppnå den maximala förväntade belöningen under alla tidsperioder, och vi får en distribuerad lösningsmetod där uppdelningen av underproblemen stämmer perfekt överens med den operativa beslutsstrukturen. För att uppnå detta samarbete bedömer och lär sig de medel som löser olika subproblem hur deras åtgärder påverkar andra delar av systemet genom icke-linjära funktionella approximationer. I stort sett fattar varje agent sina beslut för att maximera insatsernas bidrag till resten av systemet. En kommunikationsmekanism som bygger på icke-linjära funktionella approximationer medför dock särskilda utmaningar när det gäller att samordna olika agenters åtgärder. Betrakta Figur 1, Där vi illustrerar interaktionen mellan agenterna över tiden. Under den nuvarande tidsperioden t löser agenterna a, b och c sina underproblem för att maximera bidraget från sina egna beslut och effekten av deras beslut på resten av systemet. Antag att dessa agenter potentiellt kan påverka agent b vid tidpunkt t + genom att skicka resurser från de subproblem som de löser vid tidsperiod t till det subproblem som agent b kommer att lösa vid tidsperiod t +, och denna effekt uppskattas av en icke-linjär funktion av det totala antalet resurser i den framtida subproblem. Det är uppenbart att en viss agents inverkan på det framtida underproblemet beror på hur många resurser som skickas till det framtida underproblemet av de andra agenterna. Agenterna kan därför inte koncentrera sig enbart på sina egna underproblem när de bedömer hur deras beslut påverkar resten av systemet. Vi noterar att om approximationen var linjär skulle ett sådant problem inte uppstå. I detta dokument inför vi en kommunikationsmekanism som bygger på icke-linjära funktionella approximationer, som gör det möjligt för varje agens att koncentrera sig på sitt eget underproblem. Vi underlättar inlärningen av agenterna genom att uppdatera parametrarna för de funktionella approximationer adaptivt eftersom varje agent löser underproblemen under dess kontroll. Motiverad av det faktum att det förväntade marginella bidraget (vinst, intäkter, belöning, etc.) från en inkrementell resurs minskar i takt med att antalet tillgängliga resurser ökar, använder vi konkava, bitvis linjära approximationer i detta dokument. De parametrar som kännetecknar dessa approximationer är därför deras sluttningar över olika delar av deras domäner. För att uppdatera parametrarna för de funktionella approximationer, använder vi den dubbla lösningen information från subproblemen, som ungefär talar om för oss det marginella värdet av en resurs. Således, den primära lösningen används för att avgöra vilka åtgärder att vidta, och den dubbla lösningen används för att uppdatera funktionella approximationer och skapa en adaptiv inlärningsmekanism. En viktig fråga är hur väl agenterna presterar efter att ha tränats under en viss tid. För att besvara denna fråga fortsätter vi inlärningsprocessen (dvs. uppdatering av approximationer) under en viss tid. Efter denna inlärningsperiod fastställer vi parametrarna för approximationer och testar hur väl systemet fungerar med den fasta uppsättningen approximationer. Vårt arbete faller inom området distribuerad artificiell intelligens, som traditionellt har delats in i två underdiscipliner (se Bond och Gasser 1988, Gasser och Huhns 1989, O'Hare och Jennings 1996, Moulin och Chaib-Draa 1996 för en allmän översikt över området). Den första disciplinen, distribuerad problemlösning, fokuserar på informationsdelning och hantering när ett stort problem bryts ner i mindre subproblem för att få den optimala lösningen genom att lösa oberoende subproblem (se Corkill 1982, Durfee et al. 1987, påven m.fl. 1992 för representativa tillvägagångssätt). Den andra disciplinen, multiagentsystem, handlar om beteendehantering av oberoende enheter som kallas agenter (se Stone och Veloso 2000 för en nyligen genomförd undersökning). Vårt tillvägagångssätt är en distribuerad problemlösningsmetod. Detta dokument har dock kopplingar till båda disciplinerna. Motiverade både av den naturliga uppdelningen av information bland beslutsfattare i den verkliga världen och behovet av beräkningsförmåga, upplöser vi ett komplext problem i mindre subproblem. När vi får de funktionella approximationer genom den distribuerade lösningen förfarande, utvecklingen av systemet har multiagent egenskaper, som varje beslut agent nu gör sina beslut självständigt och beteendet hos agenterna samordnas med funktionella approximationer. En viktig del av vår strategi är en förstärkande inlärningsmekanism där agenten får kunskap från sina tidigare erfarenheter (dvs. den dubbla lösningen på alla underproblem som lösts av agenten). Lärandet av varje agent fångas Detta papper bygger på Topaloglu och Powell (2002) och Godfrey och Powell (2002), som formulerar vårt dynamiska resursallokeringsproblem som ett dynamiskt program och föreslår att använda separata, ickelinjära (särskilt bitvis linjära, konkava) approximationer av värdefunktionen, sönderdela problemet i tid stadier. Här tar vi den dynamiska programmering formulering av Topaloglu och Powell (2002), sönderdela varje skede av denna formulering i ännu mindre subproblem, och distribuera dem till flera medel. I exemplet med flottförvaltning som var den motiverande tillämpningen för detta arbete löser den klassiska dynamiska programmeringsformuleringen ett underproblem för varje tidsperiod. Här sönderdelas varje tidsperiod så att vi löser ett subproblem för varje tidsperiod och varje plats. Därför kallar vi detta nedbrytningssystem för rumslig nedbrytning. Adaptive learning using dynamic programmering approximations är ett forskningsområde som har varit mycket aktivt under de senaste två decennierna. Den tidigare forskningen kan delas in i två grupper beroende på hur värdefunktionens approximationer representeras. Den första gruppen representerar approximationer som enkla bordslook-up-funktioner. Detta innebär att man behåller en tabell som innehåller de ungefärliga värdefunktionsvärdena V s s  till eller de ungefärliga Q-faktorvärdena Q s a a s  på, där respektive är uppsättningarna av möjliga tillstånd och åtgärder. Det finns ett antal tekniker för att generera värdena i dessa tabeller med hjälp av bana prover av systemet, s 1 a 1 s 2 a 2, där s k och en k är kth tillstånd och åtgärd besökt. Till exempel, temporal skillnad inlärningsmetoder (Sutton 1984 (Sutton, 1988, där cs k s k+1 är den omedelbara belöningen som erhålls genom övergången från stat s k till s k+1 och är en lämplig stegstorlek. Observera att termen inom parentes är den nya uppskattningen av V s k, och vi slår samman de gamla och de nya uppskattningarna med hjälp av en enkel utjämning operation. På samma sätt uppdaterar Q-learning (Watkins 1989, Watkins och Dayan 1992) de ungefärliga Q-värdena som Q s k a k ← 1 − Q s k a k + cs k s k+1 + max a på Q s k+1 a. Vi noterar att fördelen med dessa metoder är att de inte kräver övergångssannolikheten, som kan vara svår att få tag på för praktiska problem. Upprätthållandet av tabellerna kan dock bli besvärligt om de innehåller eller innehåller många element. Det andra arbetet söker mer kompakta representationer genom att använda parameteriserade funktionella approximationer. En familj av funktioner V · r r  på n, parameteriserad av r, används som en approximation till den sanna värdefunktionen, och utmaningen är att hitta ett värde av r sådan att V · r är en "bra" approximation. Denna representation måste bibehålla värdena för endast n-parametrar, snarare än eller parametrar som i tabelluppslagningsmetoder. Offline, minsta-kvarts metoder kan användas för att passa approximationer till de värdefunktioner som uppskattas med hjälp av prov banor (Bertsekas och Tsitsiklis 1996). Alternativt, med hjälp av tidsskillnader, kan vi uppskatta parametrarna iterativt (Dayan 1992 och Tsitsiklis och Van Roy 1997 presenterar konvergensresultat i online-inställningar). När V · r är linjär i r, kan ett bra värde av r erhållas genom att lösa ett stort linjärt program utan att använda bana prover. Dessa linjära program har n variabler och begränsningar, och kräver därför vissa tillnärmningsförfarande (Schweitzer och Seidmann 1985, de Farias och Van Roy 2003). Vårt tillvägagångssätt är mer likt de parameteriserade approximationsstrategierna. Vi använder mycket kompakta representationer av värdefunktionen approximationer. För ett problem med 200 resurser och 100 state-typ par, en tabell uppslagning metod måste lagra ca 200 100 värden, medan vår strategi måste lagra ca 100 × 200 lutningsvärden. Dessutom är vårt tillvägagångssätt provtagningsbaserat och kräver inte kunskap om övergångssannolikheterna. Den slutliga och mest nya aspekten av vår strategi avslöjas när vi äntligen har en bra approximation V · r och vi vill använda den för att fatta ett beslut. Detta kräver att lösa ett problem som maximerar summan av den omedelbara belöningen och värdefunktionen approximation. Om tillnärmningen inte har någon särskild struktur kan det dock krävas uppräkning över alla möjliga lösningar för att lösa detta problem. Vi är intresserade av storskaliga tillämpningar, såsom flottförvaltning, där en sådan uppräkning är ogenomförbar. De separerade, bitvis linjära, konkava approximationer vi väljer hjälpa oss att omvandla dessa problem till min-kostnads nätverksflöde problem, där heltal lösningar erhålls mycket snabbt. I detta dokument gör vi följande forskningsbidrag: (1) Vi presenterar en distribuerad lösningsstrategi för dynamiska resursfördelningsproblem som i hög grad fångar upp den multiagentiska beslutsstrukturen i den verkliga verksamheten och utvecklar en dynamisk programplaneringsbaserad inlärningsmekanism. (2) Vi visar hur man samordnar olika subproblem för att få högkvalitativa lösningar genom att använda beräkningsbart bitvis linjära, konkava approximationer av värdefunktionen. (3) Vi bevisar att problemet minskar till att lösa sekvenser av enkla mincost nätverksflöde problem. (4) Vi illustrerar utvidgningen av vår metod för att hantera flera perioders resursomvandlingstider och få fram ett viktigt resultat som avsevärt påskyndar vårt lösningssystems prestanda. (5) Vi jämför numeriskt vår distribuerade lösningsmetod med en centraliserad metod i Topaloglu och Powell (2002) och presenterar vad vi vinner eller förlorar genom nedbrytning. I §1 definierar vi problemet, beskriver kortfattat den dynamiska programmeringsformuleringen på grund av Topaloglu och Powell (2002), och presenterar vår agentbaserade dynamiska programmeringsformulering. Avsnitt 2 beskriver den grundläggande idén om att approximera värdefunktionen och slår fast att de ungefärliga underproblemen under rumslig nedbrytning är problem med min-kostnadsnätverksflödet när vi använder separerbara, bitvis linjära, konkava värdefunktions approximationer. I avsnitt 3 sammanfattas hur värdefunktionens approximationer ska uppdateras. I avsnitt 4 presenteras en serie numeriska resultat på deterministiska och stokastiska experiment som testar den nya distribuerade lösningsmetodens lösningskvalitet. I avsnitt 5 presenteras slutsatserna.
Detta var valet för författarna i REF, där de modellerar problemet med resurstilldelning i samband med flottförvaltning.
A Distributed Decision-Making Structure for Dynamic Resource Allocation Using Nonlinear Functional Approximations
{'venue': 'Oper. Res.', 'journal': 'Oper. Res.', 'mag_field_of_study': ['Computer Science']}