didppy.CABS

class didppy.CABS(model, f_operator=Ellipsis, primal_bound=None, time_limit=None, quiet=False, initial_beam_size=1, keep_all_layers=False, max_beam_size=None, threads=1, parallelization_method=Ellipsis)

Complete Anytime Beam Search (CABS) solver.

This performs CABS using the dual bound as the heuristic function.

To apply this solver, the cost must be computed in the form of x + state_cost, x * state_cost, didppy.max(x, state_cost), or didppy.min(x, state_cost) where, state_cost is either of IntExpr.state_cost() and FloatExpr.state_cost(), and x is a value independent of state_cost. Otherwise, it cannot compute the cost correctly and may not produce the optimal solution.

CABS searches layer by layer, where the i th layer contains states that can be reached with i transitions. By default, this solver only keeps states in the current layer to check for duplicates. If keep_all_layers is True, CABS keeps states in all layers to check for duplicates.

Parameters:

  • model (Model) – DyPDL model to solve.

  • f_operator (FOperator, default: FOperator.Plus) – Operator to combine a g-value and the dual bound to compute the f-value. If the cost is computed by +, this should be Plus. If the cost is computed by *, this should be Product. If the cost is computed by max, this should be Max. If the cost is computed by min, this should be Min.

  • primal_bound (int, float, or None, default: None) – Primal bound.

  • time_limit (int, float, or None, default: None) – Time limit.

  • quiet (bool, default: False) – Suppress the log output or not.

  • initial_beam_size (int, default: 1) – Initial beam size.

  • keep_all_layers (bool, default: False) – Keep all layers of the search graph for duplicate detection in memory.

  • max_beam_size (int or None, default: None) – Maximum beam size. If None, the beam size is kept increased until proving optimality or infeasibility or reaching the time limit.

  • threads (int, default 1) – Number of threads.

  • parallelization_method (BeamParallelizationMethod, default: BeamParallelizationMethod.Hdbs2) – How to parallelize the search. When threads is 1, this parameter is ignored.

Raises:

  • TypeError – If primal_bound is float and model is int cost.

  • PanicException – If time_limit is negative.

References

Ryo Kuroiwa and J. Christopher Beck. “Solving Domain-Independent Dynamic Programming with Anytime Heuristic Search,” Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS), pp. 245-253, 2023.

Ryo Kuroiwa and J. Christopher Beck. “Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming,” Proceedings of the 38th Annual AAAI Conference on Artificial Intelligence (AAAI), 2024.

Weixiong Zhang. “Complete Anytime Beam Search,” Proceedings of the 15th National Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence (AAAI/IAAI), pp. 425-430, 1998.

Examples

Example with + operator.

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=1)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=1 + dp.IntExpr.state_cost(),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.CABS(model, quiet=True)
>>> solution = solver.search()
>>> print(solution.cost)
1

Example with max operator.

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=2)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=dp.max(x, dp.IntExpr.state_cost()),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.CABS(model, f_operator=dp.FOperator.Max, quiet=True)
>>> solution = solver.search()
>>> print(solution.cost)
2

Methods

search()

Search for the optimal solution of a DyPDL model.

search_next()

Search for the next solution of a DyPDL model.
search()

Search for the optimal solution of a DyPDL model.

Returns:

Solution.

Return type:

Solution

Raises:

PanicException – If the model is invalid.

Examples

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=1)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=1 + dp.IntExpr.state_cost(),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.CABS(model, quiet=True)
>>> solution = solver.search()
>>> solution.cost
1
search_next()

Search for the next solution of a DyPDL model.

Returns:

  • solution (Solution) – Solution.

  • terminated (bool) – Whether the search is terminated.

Raises:

PanicException – If the model is invalid.

Examples

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=1)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=1 + dp.IntExpr.state_cost(),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.CABS(model, quiet=True)
>>> solution, terminated = solver.search_next()
>>> solution.cost
1
>>> terminated
True