Abstract-I detta dokument undersöker vi problemet med att lokalisera ett icke-adversariellt mål med hjälp av flera robotiska sökare. Detta problem är relevant för många tillämpningar inom robotteknik, inklusive räddningsinsatser och flygövervakning. Förutsatt en känd miljö, detta problem blir en av att välja sökvägar som är mest sannolikt att korsa med den väg som tas av målet. Vi hänvisar till detta som Multi-robot Effektiv sökväg planering (MESPP) problem. Sådana vägplaneringsproblem är NP-hårda, och optimala lösningar brukar skala exponentiellt i antalet sökare. Vi presenterar en ändlighorizon banräkningsalgoritm för att lösa MESPP-problemet som använder sekventiell allokering för att uppnå linjär skalbarhet i antalet sökare. Vi visar att lösningen av MESPP-problemet kräver en maximering av en icke-decreasing, submodulär objektiv funktion, vilket direkt leder till teoretiska garantier för vägar som genereras av sekventiell tilldelning. Vi visar också hur vår algoritm kan köras online för att införliva bullriga mätningar av målets position under sökningen. Vi verifierar prestandan hos vår algoritm både i simulering och i experiment med en ny radiosensor som kan ge räckvidd genom väggar. Våra resultat visar att vår linjärt skalbara MESPP-algoritm genererar sökvägar som är konkurrenskraftiga med dem som genereras av exponentiella algoritmer.
Det visas i REF att explicit samordning av robotarna kommer att leda till ett sökområde som växer exponentiellt i antalet robotar.
Proofs and Experiments in Scalable , Near-Optimal Search by Multiple Robots
{'venue': 'FOCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}