# Anytime and exact search for planning problems

Christine Solnon

► To cite this version:

Christine Solnon. Anytime and exact search for planning problems. 31st International Conference on Principles and Practice of Constraint Programming (CP 2025), 2025, Glasgow, United Kingdom. 10.4230/LIPIcs.CP.2025.2 . hal-05104519

HAL Id: hal-05104519

https://hal.science/hal-05104519v1

Submitted on 10 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Anytime and exact search for planning problems

## How to explore a DP-based state transition graph with A*, CP and LS?

Christine Solnon @ ORCID

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].

**2012 ACM Subject Classification** Computing methodologies → Artificial intelligence

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

**Digital Object Identifier** 10.4230/LIPIcs.CP.2025.2

**Category** Invited Talk

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

## References

1. R. Bellman. Dynamic Programming Treatment of the Travelling Salesman Problem. *Journal of the ACM (JACM)*, 9(1):61–63, 1962.

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.

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.

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.

<figure><img src="image_2.png" /></figure>

© Christine Solnon;

licensed under Creative Commons License CC-BY 4.0

31st International Conference on Principles and Practice of Constraint Programming (CP 2025).

Editor: Maria Garcia de la Banda; Article No. 2; pp. 2:1–2:2

<figure><img src="image_3.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 2:2 Anytime and exact search for planning problems

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.

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.

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.

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.

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.

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.

11 J. J. van Hoorn. *Dynamic Programming for Routing and Scheduling: Optimizing Sequences of Decisions*. PhD thesis, Amsterdam: Vrije Universiteit, 2016.