didppy.CABS
- class didppy.CABS
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)
, ordidppy.min(x, state_cost)
where,state_cost
is either ofIntExpr.state_cost()
andFloatExpr.state_cost()
, andx
is a value independent ofstate_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
isTrue
, 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 bePlus
. If the cost is computed by*
, this should beProduct
. If the cost is computed bymax
, this should beMax
. If the cost is computed bymin
, this should beMin
.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
isfloat
andmodel
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 for the next solution of a DyPDL model.
- search()
Search for the optimal solution of a DyPDL model.
- Returns:
Solution.
- Return type:
- 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