Por qué la programación con planners es sorprendente

 (hillelwayne.com)
2 puntos por GN⁺ 2024-02-22 | 1 comentarios | Compartir por WhatsApp
  • El módulo planner de Picat va un paso más allá de la programación lógica que busca asignaciones de valores, y expresa el problema como una secuencia de cambios de estado para llegar al estado objetivo
  • Si se definen el estado inicial Start, las reglas de transición action(From, To, Action, Cost) y la condición de término final(S), best_plan(Start, Plan) encuentra el plan de costo mínimo hasta el estado final
  • En el ejemplo de rutas sobre una cuadrícula, movimientos, límites del mapa, evasión de obstáculos y visita de múltiples objetivos se manejan solo cambiando action y final, y el orden de visita de los objetivos también puede fijarse o dejarse libremente
  • La capacidad de planificación puede combinarse con resolución de restricciones, por lo que también se pueden expresar problemas como encontrar la sublista más grande que puede dividirse en sumas iguales eliminando elementos en el partition problem
  • Picat es un lenguaje de investigación, así que su documentación y sus mensajes de error son limitados, pero como lenguaje-herramienta para resolver rápido ciertos problemas computacionales puede ofrecer soluciones más concisas que un lenguaje general

La idea básica de Picat y la programación con planners

  • Picat es un lenguaje de investigación que busca combinar programación lógica, programación imperativa y resolución de restricciones
  • La programación imperativa y funcional habitual escribe algoritmos que producen una salida a partir de una entrada, mientras que la programación lógica y la resolución de restricciones buscan asignaciones de valores que satisfacen una relación
  • En Picat, los identificadores no funcionales que empiezan con minúscula son átomos como a, b, c, y los identificadores que empiezan con mayúscula son variables
  • Incluso en expresiones como member(Y, Arr), donde aparece una variable aún no definida Y, Picat puede encontrar y asignar valores que hagan verdadera la expresión
    • Si Arr = [a, b, c, a], entonces Y puede ser uno de a, b, c
    • Si después se agrega una condición como X != Y, los valores posibles se restringen más
    • Incluso cuando la propia lista aún no se conoce, como en member(a, Z), Picat puede instanciar Z como una lista

Planificar no busca asignaciones de valores, sino cambios de estado

  • En vez de buscar valores de variables que satisfagan una ecuación, la planificación busca una secuencia de cambios de variables que lleve a un estado final determinado
  • Un problema de planificación en Picat necesita tres elementos
    • El estado inicial Start
    • Las funciones action que representan transiciones de estado
    • final(S), que determina si un estado es final
  • Todas las funciones action de Picat deben llamarse action y reciben cuatro parámetros
    • Estado actual
    • Estado siguiente
    • Nombre de la acción
    • Costo
  • best_plan(Start, Plan) asigna a Plan el plan de menor número de pasos o menor costo necesario para llegar a un estado final
    • Si todos los costos se fijan en 1, el costo del plan pasa a ser el número total de movimientos
    • Si solo se necesita cualquier plan, sin importar la longitud, puede usarse plan(Start, Plan)

Ejemplo de búsqueda de rutas en una cuadrícula

  • El problema de ejemplo consiste en que un marcador sobre una cuadrícula parte del origen (0, 0) y llega a una coordenada objetivo
    • En cada paso puede moverse una celda hacia arriba, abajo, izquierda o derecha
    • No puede salir de los límites de la cuadrícula
    • Al llegar a la coordenada objetivo, tiene éxito
  • El estado inicial guarda juntos la posición actual y el objetivo, como {Origin, Goal}
    • En Picat, {a, b} es sintaxis de arreglo, pero en la práctica se usa como una tupla
  • La condición de término puede expresarse con pattern matching, como final({Pos, Goal}) => Pos = Goal.
    • Para escribir lo mismo sin pattern matching, primero habría que descomponer el estado como {Pos, Goal}
    • Si hay varias condiciones final, la planificación tiene éxito cuando cualquiera de ellas es verdadera
  • La acción de movimiento elige una de las cuatro direcciones {-1,0}, {1,0}, {0,-1}, {0,1} y comprueba que la nueva coordenada esté dentro del rango 0..10
    • member({Dx, Dy}, Dir) se usa para encontrar valores de dirección posibles
    • member(Tx, 0..10) y member(Ty, 0..10) se usan para verificar que las coordenadas estén dentro de los límites
    • También existe membchk como predicado de verificación que no asigna valores
  • El plan resultante se imprime como una lista de acciones de movimiento y nuevas coordenadas, como {move,{1,0}}, {move,{2,0}}
    • La ruta puede visualizarse con un script de Raku
    • Si se agrega una condición como {Tx, Ty} != {2, 1}, también puede hacerse evasión de obstáculos para evitar coordenadas específicas

Múltiples objetivos y minimización de costos

  • Para visitar varios objetivos, Goal deja de ser una sola coordenada y pasa a ser una cola de objetivos como [{2, 2}, {3, 4}]
  • Se agrega una nueva action que, al llegar a un objetivo, elimina ese elemento de la lista de objetivos
    • [Head|Tail] divide una lista en su primer elemento y el resto
    • Goal = [Pos|Rest] solo es verdadero cuando la posición actual Pos coincide con el primer elemento de la lista de objetivos
    • Si el nuevo estado se define como {Pos, Rest}, el objetivo alcanzado queda eliminado
  • Para saber si ya se visitaron todos los objetivos, se usa final({Pos, Goal}) => Goal = [].
    • La condición de término ya no es que la posición actual coincida con un objetivo específico, sino que la lista de objetivos esté vacía
  • Visitar los objetivos en un orden fijo no siempre produce la ruta global más corta
  • Si se quiere minimizar la ruta total ignorando el orden de los objetivos, se modifica la acción mark
    • En lugar de Goal = [Pos|Rest], se usa member(Pos, Goal) para comprobar si la posición actual aparece en cualquier parte de la lista de objetivos
    • To = {Pos, delete(Goal, Pos)} elimina de la lista el objetivo ya visitado
    • Con este enfoque, Picat puede elegir cuál objetivo visitar después para minimizar la longitud total de la ruta

Combinación de planificación y resolución de restricciones

  • La capacidad de planificación de Picat se integra con otras funciones del lenguaje, por lo que puede usarse junto con resolución de restricciones
  • El partition problem usado como ejemplo es un problema NP-completo en el que una lista de números debe dividirse en dos grupos con la misma suma
  • Este programa busca la sublista más grande de la lista original que puede dividirse en sumas iguales eliminando algunos elementos
    • Eliminar elementos de la lista de entrada se modela como una acción de planificación
    • final(Numbers) comprueba si la lista de números actual tiene una solución de partition válida
    • Con restricciones del módulo cp, cada elemento se representa con una variable 0..1 para indicar si pertenece al grupo izquierdo o al derecho
    • Se impone la restricción de que la suma total sea el doble de la suma de uno de los grupos
  • En la salida de ejemplo, después de eliminar [5,17], la lista restante puede dividirse en dos grupos con suma 1108 cada uno
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • Este enfoque no solo resuelve directamente restricciones válidas, sino que también expresa mediante planificación los cambios necesarios para llegar a un estado con restricciones válidas

Límites de Picat y casos de uso adecuados

  • Picat es un lenguaje de investigación, así que no se recomienda para uso en producción
  • No tiene muchas comodidades, y además le faltan buena documentación y mensajes de error claros
    • Cuando no existe un plan resoluble, el error aparece como *** error(failed,main/0)
  • El hecho de que pueda ejecutarse en Windows se considera una ventaja frente a muchos otros lenguajes de investigación
  • Más que un lenguaje para escribir código que se mantendrá o compartirá, Picat se parece a un lenguaje tipo toolkit orientado a resolver ciertos tipos de problemas computacionales
  • Algunos problemas que resultaban difíciles de manejar con un lenguaje de programación general y un solver de restricciones pueden resolverse con bastante elegancia en Picat

Otros lenguajes de planificación y conceptos relacionados

  • La planificación surgió originalmente en robótica e IA, pero hoy se usa con frecuencia en la IA de videojuegos con el nombre de Goal Oriented Action Planning (GOAP)
  • PDDL es un lenguaje de descripción de planificación que reciben como entrada planners independientes
    • Cumple un papel parecido al de DIMACS como formato descriptivo en SAT

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-02-22
Opiniones de Hacker News

  • He usado el modo de planificación de Picat en trabajo real
    Hice el prototipo de un sistema para coordinar el mantenimiento de varios conjuntos de equipos, y funcionaba ingresando no “cómo hacerlo”, sino “qué se quiere”, “cuáles son las acciones posibles” y “qué restricciones hay que respetar”
    En ejemplos pequeños generaba bien planes óptimos, pero al crecer a escala real se cayó como era de esperarse, y como los problemas de planificación al final son EXPTIME, las limitaciones eran grandes
    Picat tiene una vía de escape para definir heurísticas, así que hice que un random forest de predicados de estado y un clasificador Naive Bayes predijeran rutas prometedoras, pero aun agregando restricciones para romper simetrías y planificación jerárquica, requería demasiado trabajo manual
    Parece que en el ámbito clásico de problemas de GOFAI todavía queda algo de invierno de la IA
    Quizá no sea así si se reformula el problema de planificación para que devuelva “un generador en tiempo polinomial que produzca planes potencialmente exponencialmente largos”

    • Los solvers comerciales tienen mucho mejor rendimiento que los open source, y también vacían la billetera mucho más rápido
      Se me vienen a la mente CPLEX, Xpress, GUROBI y Hexaly; Hexaly es especialmente bueno para planificación de horarios o problemas de ruteo de vehículos
      Normalmente se accede a ellos mediante APIs para lenguajes muy usados en la industria, y creo que eso tiene mucho más sentido que usar lenguajes especializados de solvers que son débiles para tareas generales
      Llamar a GUROBI desde Python es muy fácil, y se pueden seguir usando las funciones generales de Python tal cual
      Mosek es mucho más barato que GUROBI, pero ambas APIs son de muy bajo nivel y su rendimiento tampoco llega al de GUROBI
    • En este caso, algo como CP-SAT(https://developers.google.com/optimization/cp) probablemente habría escalado bien
      Ese solver maneja con facilidad una cantidad absurda de variables y restricciones, y sus heurísticas incorporadas también son excelentes
    • Los planificadores antiguos reducían el espacio de búsqueda incluyendo metarreglas o heurísticas para decidir qué reglas aplicar
      Algunos sistemas dividían el problema en distintas representaciones y les conectaban solvers automáticos especializados
      Se me vienen a la mente Jahob Analysis System y Cyc
      Desde el punto de vista del uso real, el diseño más prolijo de la IA clásica fue Procedural Reasoning System, y me gustaría ver una versión reconstruida que compense sus debilidades con métodos modernos
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • Me pregunto por qué no existen solvers open source de alta calidad
      En otras áreas de cálculo numérico, muchas veces el estado del arte es open source, y siempre me he preguntado por qué el campo de la optimización es diferente
    • Viéndolo por resultados o rendimiento, me da la impresión de que no es muy distinto de una búsqueda en profundidad armada más o menos recordando vagamente a Prolog

  • En la comunidad de programación con restricciones hay un usuario activo de HN, hakank, es decir Hakan Kjellerstrand, que tiene un sitio con mucho material y ejemplos de Picat: http://www.hakank.org/picat/

  • Como de costumbre, quisiera recomendar Prolog
    Es elegante, fácil de entender y más maduro; si lo que se quiere es resolución de restricciones sobre dominios finitos, alcanza con la configuración básica
    Además, MiniZinc es una gran interfaz para acceder a varios solvers especializados en distintos propósitos, así que si no eres experto es probable que te acerque más al resultado que buscas
    Prolog tiene muchas ventajas, pero la “intuición mecánica” necesaria para obtener buen rendimiento puede volverse considerable muy rápido
    Si escribiste algo en Picat, sería bueno pensar también cómo escribirías lo mismo en otros lenguajes
    Estos problemas de juguete también son fáciles en otros lenguajes; en la mayoría de los lenguajes funcionales, Dijkstra o A* son apenas unas líneas, y muchas veces todo se reduce a definir el espacio de estados del algoritmo de búsqueda

  • Me dio gusto ver a Predrag como revisor, aunque al mismo tiempo no me sorprendió en absoluto
    Firebase technical screen habría sido mucho más fácil con una herramienta así, y al final también era otro problema de optimización
    También me dan ganas de resolverlo de nuevo con Picat
    Él también está haciendo cosas interesantes en lenguajes de programación: https://github.com/obi1kenobi/trustfall

  • Lo primero que pensé fue: “esto parece un sistema de tipos que tienes que resolver a mano”
    Intenté expresarlo ingenuamente en TypeScript, pero como a, b, c podían ser todos iguales, no resolvía nada
    Al intentar expresarlo correctamente llegué a una forma que parecía más o menos usable, pero todavía tenía que usar aserciones y tampoco podía expresar bien el tipo de Y
    Ese proceso más bien muestra lo potentes que son los programas al estilo de un planificador en términos de simplicidad y concisión
    TypeScript no parece lo suficientemente potente para expresar este tipo de restricciones
    Enlace del experimento en TS Playground: http://tinyurl.com/3p2pzdtn

  • Me gusta ver que se vuelva a mencionar GOAP
    Era el ingrediente secreto que hacía tan divertidos a los enemigos de F.E.A.R., y el paper de Jeff Orkin sobre cómo funciona también es fácil de leer y entretenido

  • Uso Prolog y algo de CLPFD en trabajo real, y es fantástico
    Ojalá estuviera en todas partes; más exactamente, quisiera tener un núcleo lógico que enfatice la pureza y empujar el comportamiento imperativo hacia los bordes
    Me da pena que la industria parezca atrapada con herramientas tan malas

  • Se ve parecido a Prolog y es interesante

  • Esta forma de programar no es completamente nueva
    Aprendí Prolog en la universidad y se ve bastante parecido, aunque Prolog no tenía funcionalidad de planificador
    Aun así, un planificador es una forma muy elegante y simple de resolver problemas
    La parte sobre videojuegos al final del artículo me dio curiosidad
    La funcionalidad de planificador permite resolver problemas muy fácilmente con unas pocas líneas de código claro, pero ¿cómo será el rendimiento comparado con un algoritmo escrito de forma imperativa?
    Picat parece bastante eficiente en comparación con lenguajes similares [1], pero no encontré una comparación con lenguajes “estándar”
    [1]: https://arxiv.org/abs/1405.2538

  • Yo también tengo el sueño de decirle a la computadora solo el estado al que debe llegar
    No conozco bien la comunidad de planificación ni los solvers, y apenas he trasteado ingenuamente con ortools, pero alguna vez generé código para ir de un estado a un estado objetivo con A*
    Generaba instrucciones de ensamblador para moverse entre estados, e incluso encontraba transiciones de estado ocultas de llamadas a funciones para llegar al objetivo
    Para acelerar la búsqueda también lo ejecuté en paralelo con Python multiprocessing, y como cada hilo generaba vecinos de forma distinta, usé generación dinámica de vecinos
    En mi intento original era difícil paralelizar A*, así que hizo falta sharding
    El sueño de mi experimento es que, si le digo a la computadora “lo que tengo ahora” y “lo que quiero”, encuentre por sí sola la ruta correcta para moverse
    Personalmente veo la programación más como logística, al estilo Factorio o una fábrica
    Por eso lo llamo “sliding puzzle”: porque es un rompecabezas en el que hay que mover cosas de un lado a otro para ver la imagen correcta
    Repositorio de GitHub y notas: https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit: https://replit.com/@Chronological/SlidingPuzzle3