Search-Based Planning

Let’s use a planner to identify the fewest US coins to provide desired total cash amount.

As described in Reasoning: Planning, the search-based planner requires four inputs:

  1. An initial state

    • 0 cents

  2. A goal predicate

    • accumulated coins == desired total

  3. A succession function

    • see below

  4. A frontier factory

    • Queue: assuming each coin is a single action, a breadth-first search is equivalent to a plan that uses the fewest coins

Note

Once developed & tested, it is common to embed planning within a DP (e.g., perform of an Operator).

We could manually build a Succession function, but this library tries to ease this burden by structuring the problem-solving knowledge via search “options”. Below you find two complete implementations, which differ (slightly) in how the succession function is implemented.

Note

In practice, static options make sense when the set of available search actions are largely the same across all search states (think dense coverage), whereas dynamic options encode search-state-specific patterns to avoid considering unnecessary options (think sparse coverage).

Static Option

A SearchPlannerStaticOption is a planning analog to an Operator within a DP: a single predicate-gated search action. Once each of them has been written, the static_opts_succession function generates a corresponding succession function.

 1"""
 2Planning coins with static options
 3"""
 4
 5from collections import Counter
 6from enum import IntEnum
 7
 8from cognition import (
 9    Queue,
10    SearchPlanner,
11    SearchPlannerStaticOption,
12    static_opts_succession,
13)
14
15# ===
16
17
18class USCoin(IntEnum):
19    """US coin name/value"""
20
21    QUARTER = 25
22    DIME = 10
23    NICKLE = 5
24    PENNY = 1
25
26
27class AddCoin(SearchPlannerStaticOption[int, USCoin]):
28    """
29    Option to add a particular coin at any time
30
31    State type: int (total cents)
32    Action type: USCoin (above)
33    """
34
35    def __init__(self, coin: USCoin):
36        super().__init__(coin)
37
38    def is_available(self, _: int) -> bool:
39        # can always add a coin (assume endless supply)
40        return True
41
42    def then(self, state: int) -> tuple[int, int]:
43        # (result = old state + coin value, cost = 1 coin)
44        return (state + self.action.value, 1)
45
46
47# ===
48
49TARGET_CENTS: int = 119
50
51planner = SearchPlanner(
52    # start with no money
53    0,
54    # goal is for total cents = target
55    lambda s: s == TARGET_CENTS,
56    # one static option per available coin
57    static_opts_succession(*(AddCoin(c) for c in USCoin)),
58    # BFS
59    Queue,
60)
61
62# attempts to build a plan
63planner.run()
64
65# run can optionally take maximum steps,
66# to maintain reactivity via iterative
67# execution; in that context, it would
68# still be searching if it hadn't found
69# a plan but still had options to explore
70assert not planner.still_searching
71
72# False if the planner hasn't produced
73# a plan that achieves the goal
74assert planner.plan_found
75
76cents = sum(c.value for c in planner.plan)
77assert cents == TARGET_CENTS
78
79# Plan (119¢): {<USCoin.QUARTER: 25>: 4, <USCoin.DIME: 10>: 1,
80#               <USCoin.NICKLE: 5>: 1, <USCoin.PENNY: 1>: 4}
81print(f"Plan ({TARGET_CENTS}¢): {dict(Counter(planner.plan))}")

Dynamic Option

A SearchPlannerDynamicOption is a planning analog to an OperatorGenerator within a DP: a pattern for producing a set of state-specific search actions. Once each of them has been written, the dynamic_opts_succession function generates a corresponding succession function.

 1"""
 2Planning coins with static options
 3"""
 4
 5from __future__ import annotations
 6
 7from collections import Counter
 8from collections.abc import Iterable
 9from enum import IntEnum
10
11from cognition import (
12    Queue,
13    SearchPlanner,
14    SearchPlannerDynamicOption,
15    dynamic_opts_succession,
16)
17
18# ===
19
20
21class USCoin(IntEnum):
22    """US coin name/value"""
23
24    QUARTER = 25
25    DIME = 10
26    NICKLE = 5
27    PENNY = 1
28
29
30class AddCoin(SearchPlannerDynamicOption[int, USCoin]):
31    """
32    Option to any coin at a particular time
33
34    State type: int (total cents)
35    Action type: USCoin (above)
36    """
37
38    def __init__(self, coin: USCoin):
39        super().__init__(coin)
40
41    @classmethod
42    def when(cls, _state: int) -> Iterable[AddCoin]:
43        # can always add any coin (assume endless supply)
44        yield from (AddCoin(c) for c in USCoin)
45
46    def then(self, state: int) -> tuple[int, int]:
47        # (result = old state + coin value, cost = 1 coin)
48        return (state + self.action.value, 1)
49
50
51# ===
52
53TARGET_CENTS: int = 119
54
55planner = SearchPlanner(
56    # start with no money
57    0,
58    # goal is for total cents = target
59    lambda s: s == TARGET_CENTS,
60    # one dynamic option covers all coins
61    dynamic_opts_succession(AddCoin),
62    # BFS
63    Queue,
64)
65
66# attempts to build a plan
67planner.run()
68
69# run can optionally take maximum steps,
70# to maintain reactivity via iterative
71# execution; in that context, it would
72# still be searching if it hadn't found
73# a plan but still had options to explore
74assert not planner.still_searching
75
76# False if the planner hasn't produced
77# a plan that achieves the goal
78assert planner.plan_found
79
80cents = sum(c.value for c in planner.plan)
81assert cents == TARGET_CENTS
82
83# Plan (119¢): {<USCoin.QUARTER: 25>: 4, <USCoin.DIME: 10>: 1,
84#               <USCoin.NICKLE: 5>: 1, <USCoin.PENNY: 1>: 4}
85print(f"Plan ({TARGET_CENTS}¢): {dict(Counter(planner.plan))}")