Koalitionsbildning är en grundläggande typ av interaktion som innebär skapandet av sammanhängande grupperingar av distinkta, autonoma, agenter för att effektivt uppnå sina individuella eller kollektiva mål. Att bilda effektiva koalitioner är en stor forskningsutmaning inom området multiagentsystem. Det centrala i denna strävan är problemet med att bestämma vilka av de många möjliga koalitionerna som skall bildas för att nå ett visst mål. Detta kräver vanligtvis att man beräknar ett värde för varje möjlig koalition, känd som koalitionsvärdet, vilket visar hur fördelaktig denna koalition skulle vara om den bildades. När dessa värden är beräknade, agenterna vanligtvis behöver för att hitta en kombination av koalitioner, där varje agent tillhör exakt en koalition, och genom vilken det övergripande resultatet av systemet maximeras. Men problemet med att skapa koalitionsstruktur är oerhört svårt på grund av antalet möjliga lösningar som måste undersökas, som ökar exponentiellt med antalet inblandade agenter. Hittills har därför många algoritmer föreslagits för att lösa detta problem med hjälp av olika tekniker - från dynamisk programmering, till heltal programmering, till stokastisk sökning - som alla lider av stora begränsningar i fråga om exekveringstid, lösningskvalitet och minneskrav. Med detta i åtanke utvecklar vi en algoritm när som helst för att lösa problemet med koalitionsstrukturgenerering. Specifikt använder algoritmen en ny representation av sökutrymmet, som delar upp utrymmet för möjliga lösningar i subrymder så att det är möjligt att beräkna övre och nedre gränser på värdena för de bästa koalitionsstrukturerna i dem. Dessa gränser används sedan för att identifiera de subrymder som inte har potential att innehålla den optimala lösningen så att de kan beskäras. Algoritmen söker därför igenom de återstående subrymderna mycket effektivt med hjälp av en gren-och-bunden teknik för att undvika att undersöka alla lösningar inom de sökta subrymderna. I denna inställning bevisar vi att vår algoritm räknar upp alla koalitionsstrukturer effektivt genom att undvika överflödiga och ogiltiga lösningar automatiskt. Dessutom, för att effektivt testa vår algoritm utvecklar vi en ny typ av indatadistribution som gör att vi kan generera mer tillförlitliga riktmärken jämfört med de indatadistributioner som tidigare använts i fältet. Med tanke på denna nya distribution, visar vi att för 27 agenter vår algoritm kan hitta lösningar som är optimala i 0,175% av den tid som krävs av den snabbaste tillgängliga algoritmen i litteraturen. Algoritmen är när som helst, och om den avbryts innan den normalt skulle ha avslutats, kan den fortfarande ge en lösning som är garanterad att vara inom en gräns från den optimala. Dessutom är de garantier vi ger om kvaliteten på lösningen betydligt bättre än de som tillhandahålls av de tidigare toppmoderna algoritmer som utformats för detta ändamål. Till exempel, i värsta fall distribution ges 25 agenter, vår algoritm kan hitta en 90% effektiv lösning på cirka 10% av tiden det tar att hitta den optimala lösningen.
I REF tillhandahålls en effektiv algoritm när som helst som använder en ny representation av sökutrymmet för att partitionera lösningsutrymmet och ta bort icke lovande delrymder.
An Anytime Algorithm for Optimal Coalition Structure Generation
{'venue': 'Journal Of Artificial Intelligence Research, Volume 34, pages 521-567, 2009', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}