Abstract-Vi presenterar distribuerade algoritmer för multirobot uppgift uppdrag där uppgifterna måste slutföras inom givna tidsfrister. Varje robot har en begränsad batteritid och därför finns det en övre gräns för den tid som den måste utföra uppgifter. Utföra varje uppgift kräver viss tid (kallas uppgift varaktighet) och varje robot kan ha olika utbetalningar för uppgifterna. Vårt problem är att tilldela uppgifterna till robotarna så att den totala payoff maximeras samtidigt som arbetet deadline begränsningar och robotens batterilivslängd begränsningar. Vårt problem är NP-hård eftersom ett specialfall av vårt problem är det klassiska generaliserade uppdragsproblemet (som är NP-hård). Det finns inga kända algoritmer (distribuerade eller centraliserade) för detta problem med bevisligen goda prestandagarantier. Vi presenterar en distribuerad algoritm för att lösa detta problem och bevisa att vår algoritm har ett approximationsförhållande på 2. För det speciella fallet av konstant uppgift varaktighet presenterar vi en distribuerad algoritm som är bevisligen nästan optimal. Våra distribuerade algoritmer är polynom i antalet robotar och antalet uppgifter. Vi presenterar även simuleringsresultat för att skildra våra algoritmers prestanda. Note to Practitioners-I detta papper presenterar vi bevisligen bra multirobot uppdragsalgoritmer, samtidigt som vi tar hänsyn till praktiska begränsningar som uppgiftsdeadlines och begränsad batteritid för robotar. Sådana begränsningar är relevanta i många tillämpningar, inklusive delar som rör sig av robotar vid tillverkning, leverans av varor från obemannade fordon samt sök- och räddningsinsatser. Vår lösning är tillämplig på en grupp heterogena robotar med olika lämplighet (dvs. belöningar) för olika uppgifter. Vårt distribuerade tillvägagångssätt är oberoende av den underliggande robotkommunikationsnätverk topologi, och därmed kan tillämpas på ett brett spektrum av robotnätverk distributioner. Slutligen är vår strategi enkel att genomföra, har låga kommunikationskrav, och den är skalbar, eftersom dess drifttid är linjär i antalet robotar och uppgifter.
Luo m.fl. presentera en distribuerad auktionsbaserad algoritm där uppgifterna måste slutföras inom givna tidsfrister REF.
Distributed Algorithms for Multirobot Task Assignment With Task Deadline Constraints
{'venue': 'IEEE Transactions on Automation Science and Engineering', 'journal': 'IEEE Transactions on Automation Science and Engineering', 'mag_field_of_study': ['Computer Science']}