Vi studerar problemet med TAPF (kombinerade måltilldelnings- och sökvägar) för team av agenter i känd terräng, som generaliserar både anonyma och icke-anonyma multiagentiska problem att hitta vägar. Varje lag får samma antal mål som det finns agenter i laget. Varje agent måste flytta till exakt ett mål ges till sitt team så att alla mål besöks. TAPF-problemet är att först tilldela agenter till mål och sedan planera kollisionsfria vägar för agenterna till sina mål på ett sådant sätt att makepan minimeras. Vi presenterar CBM (ConflictBased Min-Cost-Flow) algoritmen, en hierarkisk algoritm som löser TAPF instanser optimalt genom att kombinera idéer från anonyma och icke-anonyma multi-agent patologiska algoritmer. På låg nivå använder CBM en mincost maxflödesalgoritm på ett tidsförlängt nätverk för att tilldela alla agenter i ett enda team till mål och planera sina vägar. På hög nivå använder CBM konfliktbaserad sökning för att lösa kollisioner mellan agenter i olika team. Teoretiskt visar vi att CBM är korrekt, komplett och optimal. Experimentellt visar vi skalbarheten av CBM till TAPF instanser med dussintals team och hundratals agenter och anpassa den till ett simulerat lagersystem.
Arbetet i REF presenterar en hierarkisk algoritm som är korrekt, komplett och optimal för samtidig uppgiftstilldelning och sökväg.
Optimal Target Assignment and Path Finding for Teams of Agents
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}