didppy.CAASDy
- class didppy.CAASDy
Cost-Algebraic A* Solver for DyPDL (CAASDy).
This performs cost-algebraic A* 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.- 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 on the optimal cost (upper/lower bound for minimization/maximization).
time_limit (int, float, or None, default: None) – Time limit.
get_all_solutions (bool, default: False) – Return a new solution even if it is not improving when
search_next()
is called.quiet (bool, default: False) – Suppress the log output or not.
initial_registry_capacity (int, default: 1000000) – Initial size of the data structure storing all generated states.
- Raises:
TypeError – If
primal_bound
isfloat
andmodel
is int cost.OverflowError – If
initial_registry_capacity
is negative.PanicException – If
time_limit
is negative.
References
Ryo Kuroiwa and J. Christopher Beck. “Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization,” Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS), pp. 236-244, 2023.
Stephen Edelkamp, Shahid Jabbar, Alberto Lluch Lafuente. “Cost-Algebraic Heuristic Search,” Proceedings of the 20th National Conference on Artificial Intelligence (AAAI), pp. 1362-1367, 2005.
Peter E. Hart, Nills J. Nilsson, Bertram Raphael. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions of Systems Science and Cybernetics, vol. SSC-4(2), pp. 100-107, 1968.
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.CAASDy(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.CAASDy(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.CAASDy(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.CAASDy(model, quiet=True) >>> solution, terminated = solver.search_next() >>> solution.cost 1 >>> terminated True