Procedimiento contradictorio de la búsqueda con conocimiento heurístico

PROCEDIMIENTO CONTRADICTORIO DE LA BÚSQUEDA CON CONOCIMIENTO HEURÍSTICO

RESUMEN
Se introduce un algoritmo de planificación de confrontación basada en la búsqueda del árbol del juego, que es aplicable en modo multijugador a gran escala dominios. Con el fin de hacer frente a los problemas de escalabilidad de los la búsqueda del árbol del juego, el algoritmo utiliza el conocimiento procedimentalla captura de cómo los jugadores individuales tienden a lograr sus objetivos en el dominio, la información se utiliza para limitar la búsqueda sólo a la parte del árbol del juego que es consistente con los objetivos de los jugadores perseguir. Nosotros no imponer requisitos específicos el formato de los conocimientos de procedimiento, ninguna programación lenguaje o paradigma especificaciónagente puede ser empleados. Nosotros evaluamos el algoritmo tanto en la teoría y la empíricamente, lo que confirma que el enfoque propuesto puede conducir a una reducción sustancial de búsqueda con sólo una pequeña negativos
impacto en la calidad de las soluciones producidas.
INTRODUCCIÓN
Recientemente, ha habido un creciente interés en el estudio de los sistemas complejos, en la que un mayornúmero de agentes al mismo tiempo alcanzar sus metas, mientras que la participación en los patrones complejos de interacción mutua. Los ejemplos incluyen sistemas del mundo real, como la información y redes de comunicación o de aplicaciones de redes sociales, así como simulaciones, incluyendo los modelos de las sociedades, economías y / o la guerra. Debido a que en la mayoría de esos agentes son partede un entorno compartido único, se presentan situaciones en las que sus acciones y estrategias de interacción. Escenarios en los que el resultado de las acciones del agente depende de las acciones elegidas por los demás se denominan a menudo los juegos y han sido un interés de investigación en IA desde sus inicios. Con la creciente complejidad de los entornos en los que la agents1 interactuar, sinembargo, el juego clásico juego de algoritmos, como la búsqueda Minimax, a ser inutilizable debido a la enorme factor de ramificación, el tamaño del espacio de estado, de tiempo continuo y el espacio, y otros factores.
La AI propone soluciones para alcanzar la meta comportamiento orientado en tales ambientes, en general, pueden clasificarse en declarativas, que utilizan la formalización de losobjetivos y el uso de búsqueda de alto costo computacional de planificación, o de procedimiento, donde el conocimiento explícito de cómo alcanzar los objetivos es capturada (por lo general como algoritmos, el plan de plantillas predefinidas, o los planes) y los agentes sólo decidir qué objetivos debe ser perseguido (por ejemplo, en la mayoría de las arquitecturas BDI).
Nuestro objetivo escombinar los dos enfoques en el contexto de juego. En concreto, tomamos la búsqueda de confrontación estándar (por ejemplo, Minimax, maxn) y ampliarlo con el uso del conocimiento como un procedimiento heurístico. En la búsqueda de confrontación estándar, todas las combinaciones posibles de las acciones de todos los agentes son evaluados en el sistema hasta cierto punto (llamado lookahead), y las accionesque llevan a los mejores resultados para los agentes individuales en el ámbito de la mirada limitada por delante son elegidos a ser ejecutado. Conceptualmente, la búsqueda de confrontación realiza dos funciones independientes en paralelo:
• Planificación de agente único - para encontrar secuencias de acciones el logro de algunos objetivos parciales de los distintos agentes.
• Interacciones encuenta: - la exploración de cómo los planes de los agentes individuales interactúan unos con otros (en negativo, pero posiblemente también forma positiva)

En nuestro enfoque, reducir la complejidad de la primera tarea, empleando los conocimientos de fondo en la forma de conocimiento de los procedimientos y dejar sólo la segunda tarea a la búsqueda. En efecto, sólo las ramas que apoyan el...