Logic-Based Planning Methods

A huge body of research has been developed over the last few decades for plan- ning using logic-based representations [382, 839]. These methods usually exploit some structure that is particular to the representation. Furthermore, numerous heuristics for accelerating performance have been developed from implementation studies. The main ideas behind some of the most influential approaches are de- scribed in this section, but without presenting particular heuristics.

Rather than survey all logic-based planning methods, this section focuses on some of the main approaches that exploit logic-based representations. Keep in mind that the searching methods of Section 2.2 also apply. Once a problem is given using Formulation 2.4, the state transition graph is incrementally revealed during the search. In practice, the search graph may be huge relative to the size of the problem description. One early attempt to reduce the size of this graph was the STRIPS planning algorithm [337, 743]; it dramatically reduced the branching factor but unfortunately was not complete. The methods presented in this section represent other attempts to reduce search complexity in practice while maintaining completeness. For each method, there are some applications in which the method may be more efficient, and others for which performance may be worse. Thus, there is no clear choice of method that is independent of its particular use.

• • 1. Searching in a Space of Partial Plans

One alternative to searching directly in X is to construct partial plans without reference to particular states. By using the operator representation, partial plans can be incrementally constructed. The idea is to iteratively achieve required sub- goals in a partial plan while ensuring that no conflicts arise that could destroy the solution developed so far.

A partial plan σ is defined as

1. A set Oσ of operators that need to be applied. If the operators contain variables, these may be filled in by specific values or left as variables. The same operator may appear multiple times in Oσ , possibly with different values for the variables.
2. A partial ordering relation ≺σ on Oσ , which indicates for some pairs o1, o2 ∈

Oσ that one must appear before other: o1 ≺σ o2.

1. A set Bσ of binding constraints, in which each indicates that some variables across operators must take on the same value.
2. A set Cσ of causal links, in which each is of the form (o1, l, o2) and indicates that o1 achieves the literal l for the purpose of satisfying a precondition of o2.

Example 2.7 (A Partial Plan) Each partial plan encodes a set of possible plans. Recall the model from Example 2.6. Suppose

Oσ = {RemoveCap, Insert(Battery1)}. (2.27) A sensible ordering constraint is that

RemoveCap ≺σ Insert(Battery1). (2.28)

A causal link,

(RemoveCap, ¬On(Cap, Flashlight), Insert(Battery1)), (2.29)

indicates that the RemoveCap operator achieves the literal On(Cap, Flashlight), which is a precondition of Insert(Battery1). There are no binding constraints for this example. The partial plan implicitly represents the set of all plans for which RemoveCap appears before Insert(Battery1), under the constraint that

¬

the causal link is not violated. ．

Several algorithms have been developed to search in the space of partial plans. To obtain some intuition about the partial-plan approach, a planning algorithm is described in Figure 2.19. A vertex in the partial-plan search graph is a partial plan, and an edge is constructed by extending one partial plan to obtain another partial plan that is closer to completion. Although the general template is simple, the algorithm performance depends critically on the choice of initial plan and the particular flaw that is resolved in each iteration. One straightforward generaliza- tion is to develop multiple partial plans and decide which one to refine in each iteration.

In early works, methods based on partial plans seemed to offer substantial benefits; however, they are currently considered to be not “competitive enough” in comparison to methods that search the state space [382]. One problem is that it becomes more difficult to develop application-specific heuristics without explicit references to states. Also, the vertices in the partial-plan search graph are costly to maintain and manipulate in comparison to ordinary states.

• • 1. Building a Planning Graph

Blum and Furst introduced the notion of a planning graph, which is a power- ful data structure that encodes information about which states may be reachable [117]. For the logic-based problem expressed in Formulation 2.4, consider perform- ing reachability analysis. Breadth-first search can be used from the initial state to expand the state transition graph. In terms of the input representation, the resulting graph may be of exponential size in the number of stages. This gives precise reachability information and is guaranteed to find the goal state.

The idea of Blum and Furst is to construct a graph that is much smaller than the state transition graph and instead contains only partial information about

PLAN-SPACE PLANNING

1. Start with any initial partial plan, σ.
2. Find a flaw in σ, which may be 1) an operator precondition that has not achieved, or 2) an operator in Oσ that threatens a causal constraint in Cσ .
3. If there is no flaw, then report that σ is a complete solution and compute a linear ordering of Oσ that satisfies all constraints.
4. If the flaw is an unachieved precondition, l, for some operator o2, then find an operator, o1, that achieves it and record a new causal constraint, (o1, l, o2).
5. If the flaw is a threat on a causal link, then the threat must be removed by updating σ to induce an appropriate operator ordering, or by updating Bσ to bind the operators in a way that resolves the threat.

≺

1. Return to Step 2.

Figure 2.19: Planning in the plan space is achieved by iteratively finding a flaw in the plan and fixing it.

reachability. The resulting planning graph is polynomial in size and can be effi- ciently constructed for some challenging problems. The trade-off is that the plan- ning graph indicates states that can possibly be reached. The true reachable set is overapproximated, by eliminating many impossible states from consideration. This enables quick elimination of impossible alternatives in the search process. Planning algorithms have been developed that extract a plan from the planning graph. In the worst case, this may take exponential time, which is not surpris- ing because the problem in Formulation 2.4 is NP-hard in general. Nevertheless, dramatic performance improvements were obtained on some well-known planning benchmarks. Another way to use the planning graph is as a source of information for developing search heuristics for a particular problem.

Planning graph definition A layered graph is a graph that has its vertices partitioned into a sequence of layers, and its edges are only permitted to connect vertices between successive layers. The planning graph is a layered graph in which the layers of vertices form an alternating sequence of literals and operators:

(L1, O1, L2, O2, L3, O3, . . . , Lk, Ok, Lk+1). (2.30)

The edges are defined as follows. To each operator oi ∈ Oi, a directed edge is made from each li ∈ Li that is a precondition of oi. To each literal li ∈ Li, an edge

is made from each operator oi−1 Oi−1 that has li as an effect.

∈

One important requirement is that no variables are allowed in the operators.

Any operator from Formulation 2.4 that contains variables must be converted into

a set that contains a distinct copy of the operator for every possible substitution of values for the variables.

Layer-by-layer construction The planning graph is constructed layer by layer, starting from L1. In the first stage, L1 represents the initial state. Every positive literal in S is placed into L1, along with the negation of every positive literal not in S. Now consider stage i. The set Oi is the set of all operators for which their preconditions are a subset of Li. The set Li+1 is the union of the effects of all operators in Oi. The iterations continue until the planning graph stabilizes, which means that Oi+1 = Oi and Li+1 = Li. This situation is very similar to the stabiliza- tion of value iterations in Section 2.3.2. A trick similar to the termination action, uT , is needed even here so that plans of various lengths are properly handled. In Section 2.3.2, one job of the termination action was to prevent state transitions from occurring. The same idea is needed here. For each possible literal, l, a trivial operator is constructed for which l is the only precondition and effect. The intro- duction of trivial operators ensures that once a literal is reached, it is maintained in the planning graph for every subsequent layer of literals. Thus, each Oi may contain some trivial operators, in addition to operators from the initially given set O. These are required to ensure that the planning graph expansion reaches a steady state, in which the planning graph is identical for all future expansions.

Mutex conditions During the construction of the planning graph, information about the conflict between operators and literals within a layer is maintained. A conflict is called a mutex condition, which means that a pair of literals4 or pair of operators is mutually exclusive. Both cannot be chosen simultaneously without leading to some kind of conflict. A pair in conflict is called mutex. For each layer, a mutex relation is defined that indicates which pairs satisfy the mutex condition. A pair, o, o′ Oi, of operators is defined to be mutex if any of these conditions is met:

∈

1. Inconsistent effects: An effect of o is the negated literal of an effect of o′.
2. Interference: An effect of o is the negated literal of a precondition of o′.
3. Competing needs: A pair of preconditions, one from each of o and o′, are mutex in Li.

The last condition relies on the definition of mutex for literals, which is presented next. Any pair, l, l′ Li, of literals is defined to be mutex if at least one of the two conditions is met:

∈

1. Negated literals: l and l′ form a complementary pair.

4The pair of literals need not be a complementary pair, as defined in Section 2.4.1.

Figure 2.20: The planning graph for the flashlight example. The unlabeled oper- ator vertices correspond to trivial operators. For clarity, the operator and literal names are abbreviated.

1. Inconsistent support: Every pair of operators, o, o′ Oi−1, that achieve

∈

l and l′ is mutex. In this case, one operator must achieve l, and the other

must achieve l′. If there exists an operator that achieves both, then this condition is false, regardless of the other pairs of operators.

The mutex definition depends on the layers; therefore, it is computed layer by layer during the planning graph construction.

Example 2.8 (The Planning Graph for the Flashlight) Figure 2.20 shows the planning graph for Example 2.6. In the first layer, L1 expresses the initial state. The only applicable operator is RemoveCap. The operator layer O1 con- tains RemoveCap and three trivial operators, which are needed to maintain the literals from L1. The appearance of On(Cap, Flashlight) enables the battery- insertion operator to apply. Since variables are not allowed in operator definitions in a planning graph, two different operators (labeled as I1 and I2) appear, one for each battery. Notice the edges drawn to I1 and I2 from their preconditions. The cap may also be replaced; hence, PlaceCap is included in O2. At the L3 layer, all possible literals have been obtained. At O3, all possible operators, including the

¬

trivial ones, are included. Finally, L4 = L3, and O4 will be the same as O3. This implies that the planning graph has stabilized. ．

Plan extraction Suppose that the planning graph has been constructed up to Li. At this point, the planning graph can be searched for a solution. If no solution is found and the planning graph has stabilized, then no solution exists to the problem in general (this was shown in [117]; see also [382]). If the planning graph has not stabilized, then it can be extended further by adding Oi and Li+1. The extended graph can then be searched for a solution plan. A planning algorithm derived from the planning graph interleaves the graph extensions and the searches for solutions. Either a solution is reported at some point or the algorithm correctly reports that no solution exists after the planning graph stabilizes. The resulting algorithm is complete. One of the key observations in establishing completeness is that the literal and operator layers each increase monotonically as i increases. Furthermore, the sets of pairs that are mutex decrease monotonically, until all possible conflicts are resolved.

Rather than obtaining a fully specified plan, the planning graph yields a layered plan, which is a special form of partial plan. All of the necessary operators are included, and the layered plan is specified as

(A1, A2, . . . , Ak), (2.31)

in which each Ai is a set of operators. Within any Ai, the operators are nonmutex and may be applied in any order without altering the state obtained by the layered plan. The only constraint is that for each i from 1 to k, every operator in Ai must be applied before any operators in Ai+1 can be applied. For the flashlight example, a layered plan that would be constructed from the planning graph in Figure 2.20 is

({RemoveCap}, {Insert(Battery1), Insert(Battery2)}, {PlaceCap}). (2.32)

To obtain a fully specified plan, the layered plan needs to be linearized by specify- ing a linear ordering for the operators that is consistent with the layer constraints. For (2.32), this results in (2.24). The actual plan execution usually involves more stages than the number in the planning graph. For complicated planning prob- lems, this difference is expected to be huge. With a small number of stages, the planning graph can consider very long plans because it can apply several nonmutex operators in a single layer.

At each level, the search for a plan could be quite costly. The idea is to start from Li and perform a backward and/or search. To even begin the search, the goal literals G must be a subset of Li, and no pairs are allowed to be mutex; otherwise, immediate failure is declared. From each literal l G, an “or” part of the search tries possible operators that produce l as an effect. The “and” part of the search must achieve all literals in the precondition of an operator chosen at the previous “or” level. Each of these preconditions must be achieved, which leads to another “or” level in the search. The idea is applied recursively until the initial set L1 of literals is obtained. During the and/or search, the computed mutex relations provide information that immediately eliminates some

∈

branches. Frequently, triples and higher order tuples are checked for being mutex together, even though they are not pairwise mutex. A hash table is constructed to efficiently retrieve this information as it is considered multiple times in the search. Although the plan extraction is quite costly, superior performance was shown in

[117] on several important benchmarks. In the worst case, the search could require exponential time (otherwise, a polynomial-time algorithm would have been found to an NP-hard problem).

• • 1. Planning as Satisfiability

Another interesting approach is to convert the planning problem into an enormous Boolean satisfiability problem. This means that the planning problem of Formu- lation 2.4 can be solved by determining whether some assignment of variables is possible for a Boolean expression that leads to a true value. Generic methods for determining satisfiability can be directly applied to the Boolean expression that encodes the planning problem. The Davis-Putnam procedure is one of the most widely known algorithms for satisfiability. It performs a depth-first search by iteratively trying assignments for variables and backtracking when assignments fail. During the search, large parts of the expression can be eliminated due to the current assignments. The algorithm is complete and reasonably efficient. Its use in solving planning problems is surveyed in [382]. In practice, stochastic local search methods provide a reasonable alternative to the Davis-Putnam procedure [459].

Suppose a planning problem has been given in terms of Formulation 2.4. All literals and operators will be tagged with a stage index. For example, a literal that appears in two different stages will be considered distinct. This kind of tagging is similar to situation calculus [378]; however, in that case, variables are allowed for the tags. To obtain a finite, Boolean expression the total number of stages must be declared. Let K denote the number of stages at which operators can be applied. As usual, the fist stage is k = 1 and the final stage is k = F = K + 1. Setting a stage limit is a significant drawback of the approach because this is usually not known before the problem is solved. A planning algorithm can assume a small value for F and then gradually increase it each time the resulting Boolean expression is not satisfied. If the problem is not solvable, however, this approach iterates forever.

Let denote logical OR, and let denote logical AND. The Boolean expression is written as a conjunction5 of many terms, which arise from five different sources:

∨ ∧

1. Initial state: A conjunction of all literals in S is formed, along with the negation of all positive literals not in S. These are all tagged with 1, the initial stage index.
2. Goal state: A conjunction of all literals in G, tagged with the final stage index, F = K + 1.

5Conjunction means logical AND.

1. Operator encodings: Each operator must be copied over the stages. For each o ∈ O, let ok denote the operator applied at stage k. A conjunction is

formed over all operators at all stages. For each ok, the expression is

¬ok ∨ (p1 ∧ p2 ∧ · · · ∧ pm ∧ e1 ∧ e2 ∧ · · · ∧ en) , (2.33)

in which p1, . . ., pm are the preconditions of ok, and e1, . . ., en are the effects of ok.

1. Frame axioms: The next part is to encode the implicit assumption that every literal that is not an effect of the applied operator remains unchanged in the next stage. This can alternatively be stated as follows: If a literal l becomes negated to l, then an operator that includes l as an effect must have been executed. (If l was already a negative literal, then l is a positive literal.) For each stage and literal, an expression is needed. Suppose that lk and lk+1 are the same literal but are tagged for different stages. The expression is

¬

¬ ¬

(lk ∨ ¬lk+1) ∨ (ok,_1 ∨ o_k,_2 ∨ · · · ∨ o_k,j ), (2.34)

in which ok,_1, . . ., o_k,j are the operators, tagged for stage k, that contain lk+1 as an effect. This ensures that if lk appears, followed by lk+1, then some operator must have caused the change.

¬

1. Complete exclusion axiom: This indicates that only one operator applies at every stage. For every stage k, and any pair of stage-tagged operators ok

and o′k, the expression is

¬ok ∨ ¬o′k, (2.35)

which is logically equivalent to (ok o′k) (meaning, “not both at the same stage”).

¬ ∧

It is shown in [512] that a solution plan exists if and only if the resulting Boolean expression is satisfiable.

The following example illustrates the construction.

Example 2.9 (The Flashlight Problem as a Boolean Expression) A Boolean expression will be constructed for Example 2.6. Each of the expressions given be- low is joined into one large expression by connecting them with ’s.

∧

The expression for the initial state is

O(C, F, 1) ∧ ¬I(B1, F, 1) ∧ ¬I(B2, F, 1), (2.36)

which uses the abbreviated names, and the stage tag has been added as an argu- ment to the predicates. The expression for the goal state is

O(C, F, 5) ∧ I(B1, F, 5) ∧ I(B2, F, 5), (2.37)

which indicates that the goal must be achieved at stage k = 5. This value was determined because we already know the solution plan from (2.24). The method

will also work correctly for a larger value of k. The expressions for the operators are

¬PCk ∨ (¬O(C, F, k) ∧ O(C, F, k + 1))

¬RCk ∨ (O(C, F, k) ∧ ¬O(C, F, k + 1))

¬I1k ∨ (¬O(C, F, k) ∧ ¬I(B1, F, k) ∧ I(B1, F, k + 1))

¬I2k ∨ (¬O(C, F, k) ∧ ¬I(B2, F, k) ∧ I(B2, F, k + 1))

for each k from 1 to 4.

The frame axioms yield the expressions

(O(C, F, k) ∨ ¬O(C, F, k + 1)) ∨ (PCk)

(¬O(C, F, k) ∨ O(C, F, k + 1)) ∨ (RCk)

(I(B1, F, k) ∨ ¬I(B1, F, k + 1)) ∨ (I1k)

(¬I(B1, F, k) ∨ I(B1, F, k + 1))

(I(B2, F, k) ∨ ¬I(B2, F, k + 1)) ∨ (I2k)

(¬I(B2, F, k) ∨ I(B2, F, k + 1)),

(2.38)

(2.39)

for each k from 1 to 4. No operators remove batteries from the flashlight. Hence, two of the expressions list no operators.

Finally, the complete exclusion axiom yields the expressions

¬RCk ∨ ¬PCk ¬RCk ∨ ¬O1k ¬RCk ∨ ¬O2k (2.40)

¬PCk ∨ ¬O1k ¬PCk ∨ ¬O2k ¬O1k ∨ ¬O2k,

for each k from 1 to 4. The full problem is encoded by combining all of the given expressions into an enormous conjunction. The expression is satisfied by assign- ing true values to RC1, IB12, IB23, and PC4. An alternative solution is RC1,

IB22, IB13, and PC4. The stage index tags indicate the order that the actions are applied in the recovered plan. ．

Further Reading

Most of the ideas and methods in this chapter have been known for decades. Most of the search algorithms of Section 2.2 are covered in algorithms literature as graph search [243, 404, 692, 857] and in AI literature as planning or search methods [551,

743, 744, 777, 839, 975]. Many historical references to search in AI appear in [839]. Bidirectional search was introduced in [797, 798] and is closely related to means-end analysis [735]; more discussion of bidirectional search appears in [185, 184, 497, 569, 839]. The development of good search heuristics is critical to many applications of discrete

planning. For substantial material on this topic, see [382, 550, 777]. For the relationship between planning and scheduling, see [266, 382, 896].

Figure 2.21: Another five-state discrete planning problem.

The dynamic programming principle forms the basis of optimal control theory and many algorithms in computer science. The main ideas follow from Bellman’s principle of optimality [84, 85]. These classic works led directly to the value-iteration methods of Section 2.3. For more recent material on this topic, see [95], which includes Dijkstra’s algorithm and its generalization to label-correcting algorithms. An important special version of Dijkstra’s algorithm is Dial’s algorithm [272] (see [946] and Section 8.2.3). Throughout this book, there are close connections between planning methods and control theory. One step in this direction was taken earlier in [267].

The foundations of logic-based planning emerged from early work of Nilsson [337, 743], which contains most of the concepts introduced in Section 2.4. Over the last few decades, an enormous body of literature has been developed. Section 2.5 briefly surveyed some of the highlights; however, several more chapters would be needed to do this subject justice. For a comprehensive, recent treatment of logic-based planning, see [382]; topics beyond those covered here include constraint-satisfaction planning, scheduling, and temporal logic. Other sources for logic-based planning include [378, 839, 963, 984]. A critique of benchmarks used for comparisons of logic-based planning algorithms appears in [464].

Too add uncertainty or multiple decision makers to the problems covered in this chapter, jump ahead to Chapter 10 (this may require some background from Chapter 9). To move from searching in discrete to continuous spaces, try Chapters 5 and 6 (some background from Chapters 3 and 4 is required).

Exercises

1. Consider the planning problem shown in Figure 2.21. Let a be the initial state, and let e be the goal state.
   1. Use backward value iteration to determine the stationary cost-to-go.
   2. Do the same but instead use forward value iteration.
2. Try to construct a worst-case example for best-first search that has properties similar to that shown in Figure 2.5, but instead involves moving in a 2D world with obstacles, as introduced in Example 2.1.
3. It turns out that value iteration can be generalized to a cost functional of the form

K

-

L(πK ) = l(xk, uk, xk+1) + lF (xF ), (2.41)

k=1

in which l(xk, uk) in (2.4) has been replaced by l(xk, uk, xk+1).

• 1. Show that the dynamic programming principle can be applied in this more general setting to obtain forward and backward value iteration methods that solve the fixed-length optimal planning problem.
  2. Do the same but for the more general problem of variable-length plans, which uses termination conditions.

• The cost functional can be generalized to being stage-dependent, which means that the cost might depend on the particular stage k in addition to the state, xk and the action uk. Extend the forward and backward value iteration methods of

Section 2.3.1 to work for this case, and show that they give optimal solutions. Each term of the more general cost functional should be denoted as l(xk, uk, k).

1. Recall from Section 2.3.2 the method of defining a termination action uT to make the value iterations work correctly for variable-length planning. Instead of re- quiring that one remains at the same state, it is also possible to formulate the

problem by creating a special state, called the terminal state, xT . Whenever uT

is applied, the state becomes xT . Describe in detail how to modify the cost func-

tional, state transition equation, and any other necessary components so that the value iterations correctly compute shortest plans.

1. Dijkstra’s algorithm was presented as a kind of forward search in Section 2.2.1.
   1. Develop a backward version of Dijkstra’s algorithm that starts from the goal. Show that it always yields optimal plans.
   2. Describe the relationship between the algorithm from part (a) and the back- ward value iterations from Section 2.3.2.
   3. Derive a backward version of the A∗ algorithm and show that it yields optimal plans.
2. Reformulate the general forward search algorithm of Section 2.2.1 so that it is expressed in terms of the STRIPS-like representation. Carefully consider what needs to be explicitly constructed by a planning algorithm and what is considered only implicitly.
3. Rather than using bit strings, develop a set-based formulation of the logic-based planning problem. A state in this case can be expressed as a set of positive literals.
4. Extend Formulation 2.4 to allow disjunctive goal sets (there are alternative sets of literals that must be satisfied). How does this affect the binary string represen- tation?
5. Make a Remove operator for Example 2.17 that takes a battery away from the flashlight. For this operator to apply, the battery must be in the flashlight and must not be blocked by another battery. Extend the model to allow enough information for the Remove operator to function properly.
6. Model the operation of the sliding-tile puzzle in Figure 1.1b using the STRIPS-like representation. You may use variables in the operator definitions.
7. Find the complete set of plans that are implicitly encoded by Example 2.7.
8. Explain why, in Formulation 2.4, G needs to include both positive and negative literals, whereas S only needs positive literals. As an alternative definition, could S have contained only negative literals? Explain.
9. Using Formulation 2.4, model a problem in which a robot checks to determine whether a room is dark, moves to a light switch, and flips on the light. Predicates should indicate whether the robot is at the light switch and whether the light is on. Operators that move the robot and flip the switch are needed.
10. Construct a planning graph for the model developed in Exercise 14.
11. Express the model in Exercise 14 as a Boolean satisfiability problem.
12. In the worst case, how many terms are needed for the Boolean expression for planning as satisfiability? Express your answer in terms of |I|, |P |, |O|, |S|, and

|G|.

Implementations

1. Using A∗ search, the performance degrades substantially when there are many alternative solutions that are all optimal, or at least close to optimal. Implement A∗ search and evaluate it on various grid-based problems, based on Example 2.1. Compare the performance for two different cases:
   1. Using |i′ − i| + |j′ − j| as the heuristic, as suggested in Section 2.2.2.
   2. Using (i′ − i)2 + (j′ − j)2 as the heuristic. Which heuristic seems superior? Explain your answer.

/

1. Implement A∗, breadth-first, and best-first search for grid-based problems. For each search algorithm, design and demonstrate examples for which one is clearly better than the other two.
2. Experiment with bidirectional search for grid-based planning. Try to understand and explain the trade-off between exploring the state space and the cost of con- necting the trees.
3. Try to improve the method used to solve Exercise 18 by detecting when the search might be caught in a local minimum and performing random walks to try to escape. Try using best-first search instead of A∗. There is great flexibility in possible approaches. Can you obtain better performance on average for any particular examples?
4. Implement backward value iteration and verify its correctness by reconstructing the costs obtained in Example 2.5. Test the implementation on some complicated examples.
5. For a planning problem under Formulation 2.3, implement both Dijkstra’s algo- rithm and forward value iteration. Verify that these find the same plans. Comment on their differences in performance.
6. Consider grid-based problems for which there are mostly large, open rooms. At- tempt to develop a multi-resolution search algorithm that first attempts to take larger steps, and only takes smaller steps as larger steps fail. Implement your ideas, conduct experiments on examples, and refine your approach accordingly.