Probabilistic Focal Search: azar para mover la cota inferior

Focal Search arrastra una ineficiencia concreta desde su formulación: el nodo que elige la heurística secundaria puede no mover la cota inferior durante cientos de expansiones. Mientras f_min no sube, FOCAL no crece, y los nodos que llevarían a una solución aceptable siguen fuera del conjunto elegible. El trabajo Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement, publicado en arXiv el 12 de septiembre, ataca eso con un cambio que cabe en una línea de código.

La búsqueda acotada subóptima (bounded suboptimal search) busca una solución que no sea peor que un factor w del óptimo, a cambio de explorar mucho menos que una búsqueda exacta. Focal Search lo consigue con dos colas: OPEN, ordenada por f, y FOCAL, el subconjunto de nodos frontera cuyo f no supera w por f_min. Dentro de FOCAL decide una heurística secundaria, normalmente más barata o mejor informada sobre la distancia real al objetivo.

El cambio: una moneda al aire

PFS introduce un parámetro p. Con probabilidad p hace lo que haría Focal Search, seguir la guía secundaria dentro de FOCAL. Con probabilidad 1 menos p expande el nodo de menor f de OPEN, que es justo el movimiento capaz de subir f_min. Al subir f_min sube también el umbral w por f_min, FOCAL se ensancha y entran nodos que hasta entonces no eran elegibles.

Dicho de otro modo, el algoritmo reparte su presupuesto entre dos objetivos que compiten: aprovechar la guía y garantizar que la cota avanza. Cuando el cuello de botella es la admisión tardía en FOCAL, y no la calidad de la heurística, gastar una fracción de las expansiones en mover la cota sale a cuenta.

Dónde lo prueban

Los autores comparan PFS con FS en tres dominios clásicos: N-Puzzle, pancake sorting y el problema del viajante (TSP), con varios valores de w y de p. Añaden la evaluación de una extensión anytime sobre el Generalized Covering TSP. Y como experimento de transferencia aplican el mismo planificador probabilístico a Dynamic Potential Search, del que sale Probabilistic Dynamic Potential Search (PDPS).

El resumen público en arXiv se corta justo donde empezaba a dar la magnitud de la mejora, así que la cifra hay que ir a buscarla al PDF. Es un aviso pertinente: en un trabajo así lo interesante no es que mejore, es cuánto y en qué régimen de w. Un algoritmo con w de 1,05 y otro con w de 2 viven en mundos distintos, y el segundo tolera mucho más desorden en la política de expansión.

Para quién importa

El público directo de un trabajo así es estrecho, pero está bien definido:

Planificación de rutas y multi-agent path finding, en almacenes, flotas AGV o videojuegos, donde Focal Search y sus variantes son el estándar de facto cuando el óptimo no es rentable.
Equipos de optimización combinatoria que ya usan búsqueda acotada y pueden probar el cambio sin reescribir el planificador entero.
* Cualquiera que combine una heurística aprendida con una búsqueda con garantías: el patrón de PFS, mezclar una política guiada con un movimiento que asegura progreso de la cota, no depende de dónde venga la guía.

Ese último punto es el que conecta con el trabajo diario de quien monta agentes. Cuando la guía la da un modelo, la tentación es seguirla siempre. PFS recuerda el valor de reservar una fracción del presupuesto a un movimiento que garantice progreso medible, aunque a corto plazo parezca peor. Con una diferencia importante: en búsqueda ese progreso está definido formalmente, la cota sube o no sube, y en un agente basado en LLM casi nunca lo está.

Nuestra valoración es que el atractivo de PFS está en lo barato que resulta probarlo, un parámetro y una rama en la política de expansión. Su precio es ese mismo parámetro, porque un p que funciona en N-Puzzle no tiene por qué funcionar en tu dominio, y ajustarlo es trabajo empírico que el paper no te va a ahorrar.