Anytime and Exact Search for Planning Problems: How to Explore a DP-based State Transition Graph with A*, CP and LS? (Invited Talk)

Solnon, Christine

doi:10.4230/LIPIcs.SAT.2025.2

Anytime and Exact Search for Planning Problems

Christine Solnon

Univ Lyon, INSA Lyon, Inria, CITI, EA3720, 69621 Villeurbanne, France

Abstract

Many planning problems may be solved with Dynamic Programming (DP) by decomposing the problem into subproblems which are recursively solved. These decompositions induce state transition graphs which are closely related to decision diagrams [5], and where optimal solutions correspond to best paths in these graphs. A* is a well known algorithm which extends Djikstra’s algorithm with heuristics for guiding the path search [4]. It is exact (provided that the heuristic function is admissible), but it is not anytime. In other words, it computes a best path but it does not output sub-optimal paths while computing it. Hence, when state transition graphs have exponential sizes, A* may run out of time or memory without producing any solution. Various anytime extensions of A* have been proposed to compute a sequence of paths of increasing quality until finding an optimal path and proving its optimality.

In this talk, we will provide an overview of these exact and anytime extensions of A*, with a more detailed focus on Anytime Column Search (ACS) [10], and Iterative Memory Bounded A* (IMBA*) [6]. Both approaches iterate A* searches while bounding the number of states that are stored or expanded at each iteration. We will also show how to combine them with Local Search (LS) in order to find better paths faster, and with bounding and constraint propagation in order to prune the graph, as proposed in [3].

This will be illustrated using the Travelling Salesman Problem (TSP) as a running example. The DP formulation introduced by Bellman in [1] for the TSP has been extended to handle Time Windows (TWs) in [2], and Time Dependent (TD) cost functions in [7]. It has also been extended to Vehicle Routing Problems (VRPs) in [11] and to TD-VRPs in [8]. We will finish by presenting an experimental comparison with state-of-the-art approaches for solving the TSP with TWs on classical benchmarks and on a new benchmark which contains hard Euclidean instances located in the phase transition zone [9].

Keywords and phrases:

Dynamic Programming, A*, Anytime search, Time Dependent TSP-TW

Category:

Invited Talk

Copyright and License:

2012 ACM Subject Classification:

Computing methodologies

\rightarrow

Artificial intelligence

Funding:

The author acknowledges the support of the French Agence Nationale de la Recherche (ANR), under grant ANR-22-CE22-0016-01 (project MAMUT).

DOI:

10.4230/LIPIcs.SAT.2025.2

Event:

28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Editors:

Jeremias Berg and Jakob Nordström

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

References

[1] R. Bellman. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM (JACM), 9(1):61–63, 1962. doi:10.1145/321105.321111.
[2] N. Christofides, A. Mingozzi, and P. Toth. State-space relaxation procedures for the computation of bounds to routing problems. Networks, 11(2):145–164, 1981. doi:10.1002/NET.3230110207.
[3] R. Fontaine, J. Dibangoye, and C. Solnon. Exact and anytime approach for solving the time dependent traveling salesman problem with time windows. Eur. J. Oper. Res., 311(3):833–844, 2023. doi:10.1016/J.EJOR.2023.06.001.
[4] P. E. Hart, N. J. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Trans. Syst. Sci. Cybern., 4(2):100–107, 1968. doi:10.1109/TSSC.1968.300136.
[5] J. N. Hooker. Decision diagrams and dynamic programming. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, volume 7874 of LNCS, pages 94–110. Springer, 2013. doi:10.1007/978-3-642-38171-3_7.
[6] L. Libralesso and F. Fontan. An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem. Eur. J. Oper. Res., 291(3):883–893, 2021. doi:10.1016/J.EJOR.2020.10.050.
[7] C. Malandraki and R. B. Dial. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. Eur. J. Oper. Res., 90(1):45–55, 1996. doi:10.1016/0377-2217(94)00299-1.
[8] O. Rifki, N. Chiabaut, and C. Solnon. On the impact of spatio-temporal granularity of traffic conditions on the quality of pickup and delivery optimal tours. Transportation Research Part E: Logistics and Transportation Review, 142, 2020. doi:10.1016/j.tre.2020.102085.
[9] O. Rifki and C. Solnon. On the phase transition of the euclidean travelling salesman problem with time windows. J. Artif. Intell. Res., 82:2167–2188, 2025. doi:10.1613/JAIR.1.18334.
[10] S. G. Vadlamudi, P. Gaurav, S. Aine, and P. P. Chakrabarti. Anytime Column Search. In AI 2012: Advances in Artificial Intelligence - 25th Australasian Joint Conference, volume 7691 of LNCS, pages 254–265. Springer, 2012. doi:10.1007/978-3-642-35101-3_22.
[11] J. J. van Hoorn. Dynamic Programming for Routing and Scheduling: Optimizing Sequences of Decisions. PhD thesis, Amsterdam: Vrije Universiteit, 2016. URL: https://research.vu.nl/files/42163578/complete%20dissertation.pdf.

[bib.bib1] [1] R. Bellman. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM (JACM), 9(1):61–63, 1962. doi:10.1145/321105.321111.

[bib.bib2] [2] N. Christofides, A. Mingozzi, and P. Toth. State-space relaxation procedures for the computation of bounds to routing problems. Networks, 11(2):145–164, 1981. doi:10.1002/NET.3230110207.

[bib.bib3] [3] R. Fontaine, J. Dibangoye, and C. Solnon. Exact and anytime approach for solving the time dependent traveling salesman problem with time windows. Eur. J. Oper. Res., 311(3):833–844, 2023. doi:10.1016/J.EJOR.2023.06.001.

[bib.bib4] [4] P. E. Hart, N. J. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Trans. Syst. Sci. Cybern., 4(2):100–107, 1968. doi:10.1109/TSSC.1968.300136.

[bib.bib5] [5] J. N. Hooker. Decision diagrams and dynamic programming. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, volume 7874 of LNCS, pages 94–110. Springer, 2013. doi:10.1007/978-3-642-38171-3_7.

[bib.bib6] [6] L. Libralesso and F. Fontan. An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem. Eur. J. Oper. Res., 291(3):883–893, 2021. doi:10.1016/J.EJOR.2020.10.050.

[bib.bib7] [7] C. Malandraki and R. B. Dial. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. Eur. J. Oper. Res., 90(1):45–55, 1996. doi:10.1016/0377-2217(94)00299-1.

[bib.bib8] [8] O. Rifki, N. Chiabaut, and C. Solnon. On the impact of spatio-temporal granularity of traffic conditions on the quality of pickup and delivery optimal tours. Transportation Research Part E: Logistics and Transportation Review, 142, 2020. doi:10.1016/j.tre.2020.102085.

[bib.bib9] [9] O. Rifki and C. Solnon. On the phase transition of the euclidean travelling salesman problem with time windows. J. Artif. Intell. Res., 82:2167–2188, 2025. doi:10.1613/JAIR.1.18334.

[bib.bib10] [10] S. G. Vadlamudi, P. Gaurav, S. Aine, and P. P. Chakrabarti. Anytime Column Search. In AI 2012: Advances in Artificial Intelligence - 25th Australasian Joint Conference, volume 7691 of LNCS, pages 254–265. Springer, 2012. doi:10.1007/978-3-642-35101-3_22.

[bib.bib11] [11] J. J. van Hoorn. Dynamic Programming for Routing and Scheduling: Optimizing Sequences of Decisions. PhD thesis, Amsterdam: Vrije Universiteit, 2016. URL: https://research.vu.nl/files/42163578/complete%20dissertation.pdf.