Luego de reunirme con mi tutor, se decidió que la propuesta estará enfocada en el desarrollo de un nuevo algoritmo para resolver el problema de búsqueda multiagente.

“¿Con qué se come eso?” -capaz se pregunten-. Para ejemplificarlo y no ponernos tan formales (aun), arrancamos con el problema de búsqueda simple. Tenemos un grafo conexo en donde el problema es encontrar la mejor ruta, si existe, entre un vértice origen y un vértice destino para un agente. Sencillo, aplicamos A* y santo remedio; tenemos búsqueda.

Un montón de problemas en computación se pueden resolver modelandose en grafo y aplicando algoritmos de búsqueda simple. Pero hay otros problemas interesantes (sí, ésa palabra que denota que el problema es yuca y que estoy casi seguro que tu profesor[a] de mate también la usa) que pueden modelarse de la misma manera y agregando restricciones:

  • Existen k número de agentes, tal que k es igual o mayor a uno y menor o igual al número de vértices en el grafo.
  • Dos o más agentes no pueden estar en un vértice al mismo tiempo, por lo cual cada agente tiene un vértice orígen y destino únicos.
  • Dos agentes en vértices adyacentes no pueden cruzar por la misma arista para cambiar de posición.

El problema tiene aplicaciones en el mundo de la robótica, enrutamiento de vehículos y, entre otros, el de los videojuegos. Lo más directo sería modelar cada agente como un bot  y el espacio de desplazamiento se encuentra segmentado en un grafo y el objetivo es lograr que los bots lleguen a sus posiciones estratégicas con el menor costo posible. De hecho, este paper ofrece una solución al problema pero, a pesar de ser eficiente, no lo resuelve por completo además de tener deficiencias técnicas.

Una instancia del problema de búsqueda multi-agente es el problema 15-puzzle o sliding puzzle (porque no tengo ni idea de cómo se llama en Español), por eso lo tomé como imagen principal para la entrada; porque poner un grafo es demasiado mainstream 😛

En los últimos años se ha buscado desarrollar soluciones que no sólo sean completas (que resuelvan el problema para cualquier entrada), sino también eficientes. Sin embargo, dependiendo de factores como número de agentes y densidad del grafo, las soluciones propuestas hasta el momento presentan ventajas y desventajas; por lo que es interesante el estudio de sus características a fin de encontrar una solución general.

En la próxima entrada tocaré el tema ya desde un punto de vista más formal y hablaré un poco de los antecedentes de la investigación.