miniatura|Exemple de cerca de camins multi-agent en un entorn de quadrícula. El problema de la cerca de camins multiagent (MAPF) és un exemple de planificació multiagent i consisteix en el càlcul de camins lliures de col·lisions per a un grup d'agents des de la seva ubicació fins a un objectiu assignat. És un problema d'optimització, ja que l'objectiu és trobar aquells camins que optimitzin una funció objectiu determinada, normalment definida com el nombre de passos de temps fins que tots els agents arriben a les seves cel·les objectiu. La MAPF és la generalització multiagent del problema de cerca de camins i està estretament relacionada amb el problema del camí més curt en el context de la teoria de grafs.

S'han proposat diversos algoritmes per resoldre el problema MAPF. A causa de la seva complexitat, passa que els enfocaments òptims no són factibles en entorns grans i amb un nombre elevat d'agents. Tanmateix, ateses les aplicacions en què participa MAPF, com ara magatzems automatitzats i gestió d'aeroports, és important arribar a un compromís entre l'eficiència de la solució i la seva eficàcia.

Formalització del problema Els elements d'un problema MAPF clàssic són els següents:

un conjunt de agents; un graf no dirigit , on és el conjunt de nodes, i és el conjunt de vores. Els nodes representen les possibles ubicacions dels agents, mentre que els arcs són les possibles connexions entre aquestes posicions; un mapa que associa cada agent amb el seu punt de partida; un mapa que associa cada agent amb el seu punt objectiu.

Se suposa que el temps és discret i que cada agent pot realitzar una acció a cada pas de temps. Hi ha dos tipus d'accions possibles: l'acció d'espera, en què l'agent roman al seu node, i l'acció de moviment, que permet a l'agent moure's a un node adjacent. Una acció es formalitza com una funció , és a dir que representa l'acció de passar de a si és adjacent a i diferent de , o per romandre al node si .

Els agents realitzen seqüències d'accions per anar des del seu punt de partida fins a la seva ubicació de destinació. Una seqüència d'accions realitzades per un agent es denota per i s'anomena pla. Si l'agent comença des de la seva ubicació i arriba a la seva ubicació de destinació realitzant un pla , aleshores s'anomena pla d'agent únic per a agent Una solució vàlida per al problema MAPF és un conjunt de plans d'un sol agent (un per a cada agent), de manera que els plans no xoquin entre si. Un cop un agent ha arribat al seu objectiu, pot romandre a la ubicació objectiu o desaparèixer.

Tipus de col·lisions Per tal de tenir una solució vàlida per a un problema MAPF, és necessari que els plans d'agent únic del els agents no xoquen entre si. Pla donat , l'expressió denota la posició de l'agent després d'haver realitzat passos del pla . És possible distingir cinc tipus diferents de col·lisions entre dos plans i miniatura|Tipus de conflictes: (a) és un conflicte d'aresta, (b) un conflicte de vèrtex, (c) un conflicte de seguiment, (d) un conflicte de cicle i (e) un conflicte d'intercanvi.

Conflicte de vèrtexs: hi ha un conflicte de vèrtexs entre plans i quan els dos agents ocupen la mateixa ubicació alhora. Formalment, un conflicte de vèrtexs es produeix quan . Conflicte de vora: un conflicte de vora es produeix quan dos agents creuen la mateixa vora en la mateixa direcció alhora, és a dir, i . Si no es permeten conflictes de vèrtexs, aleshores no poden existir conflictes d'arestes. Conflicte de seguiment: un conflicte de seguiment es produeix quan en un determinat pas de temps un agent ocupa una ubicació que estava ocupada per un altre agent en el pas de temps anterior. Matemàticament, un conflicte següent es descriu com . Conflicte cíclic: un conflicte cíclic es produeix quan un conjunt d'agents (almenys tres) es mouen com si estiguessin girant en un cicle. Significa que cada agent ocupa la posició que anteriorment ocupava l'altre agent un pas per davant en el cicle. Si els conflictes següents estan prohibits, aleshores els conflictes de cicle no poden produir-se. Conflicte d'intercanvi: un conflicte d'intercanvi és el cas en què dos agents intercanvien les seves posicions, passant per la mateixa vora al mateix temps en dues direccions diferents. S'expressa com i .

Quan es formalitza un problema MAPF, és possible decidir quins conflictes estan permesos i quins estan prohibits. No existeix un estàndard unificat sobre conflictes permesos i denegats, però els conflictes de vèrtexs i arestes no solen estar permesos.

Funcions Objectives Quan es calculen plans d'un sol agent, l'objectiu és maximitzar una funció objectiu definida per l'usuari. No hi ha una funció objectiu estàndard a adoptar, però les més comunes són:

temps de flux: aquesta mesura s'obté sumant els passos de temps emprats per cada agent per arribar a la seva ubicació objectiu. Formalment, és igual a , on els plans són plans d'agent únic sense col·lisions; makespan: el nombre de passos de temps necessaris perquè tots els agents completin les seves tasques, definit com , on formen part d'una solució vàlida; maximització dels objectius assolits donat un termini de temps: l'objectiu és trobar una solució vàlida que maximitzi el nombre d'agents que aconsegueixen el seu objectiu donat un termini de temps.

Algorismes S'han proposat diversos algoritmes per resoldre el problema MAPF. El problema és que és NP-difícil trobar solucions òptimes de makespan o flow-time, també quan es consideren grafs planars, grafs similars a quadrícules, grafs d'arbre fins i tot quan l'arbre té un nombre limitat de fulles o un nombre limitat de vèrtexs interns. Pel que fa a les solucions subòptimes limitades, es demostra que és NP-difícil trobar una solució makespan-òptima amb un factor de subòptimalitat menor que Els solucionadors MAPF òptims retornen solucions d'alta qualitat, però la seva eficiència és baixa. En canvi, els solucionadors subòptims i subòptims limitats són més eficients, però les seves solucions són menys efectives. També s'han proposat mètodes d'aprenentatge automàtic per resoldre el problema MAPF.

Aplicacions MAPF es pot aplicar en diversos casos reals:

Magatzems automatitzats: la logística de magatzems representa la principal aplicació industrial de MAPF. S'ha demostrat que l'automatització en magatzems aconsegueix augmentar el nivell de productivitat. Operacions aeroportuàries: els algoritmes MAPF es poden utilitzar en aeroports concorreguts per coordinar els vehicles de remolc que transporten aeronaus. Poder optimitzar aquest tipus de problemes també proporciona un benefici per al medi ambient. Robots de servei mòbils autònoms: els robots de servei són agents automatitzats que realitzen tasques perilloses i repetitives per als humans en un entorn no industrial. El seu principal objectiu és ajudar els éssers humans. Videojocs: la utilitat de MAPF en aquests entorns es pot trobar quan el jugador ha de moure un equip d'agents en un entorn de videojoc congestionat.

Referències

Categoria:Teoria de grafs