Keep the corrected one-place STRIPS model, replace the item constants and their initial typing facts by , and require all three west in the goal. The farmer travels with the boat, so the boat's bank also records where supervision is available. The new requirement concerns the bank being left: incompatible items may coexist at the farmer's current bank, but must not be left there together.
Here is a compilation using only ordinary positive STRIPS preconditions. Replace everywhere by , extending the item's possible locations to
The boat itself still has only bank locations, enforced by . Initialize a static relation for every and bank except . It states that two incompatible items at locations are not both on the bank about to be left.
Introduce planning safety certificates and , neither initially true. The following checking action grants a certificate:
Add to the preconditions of . Every load, unload and move deletes both certificate facts. The other movement and capacity effects remain unchanged.
Deleting certificates on every location change prevents a stale safety check from authorizing a later unsafe departure. A certificate is granted only for the actual current locations and only when both incompatible pairs are separated on the departure bank. During a crossing the remaining bank is therefore safe; on arrival the farmer supervises the destination bank. This proves the required safety property by mathematical induction over crossings. The static facts are never changed.
Partition the items into successive groups of size two, with a singleton final group if is odd. For a pair on the east bank, execute
For a singleton , execute
Return the empty boat east between groups. Each group starts and ends with marker , and its items finish west, proving all preconditions and the final goal by mathematical induction over the groups. For there are outward journeys and crossings in total; is the ceiling function. Again needs no actions.
Replace the one-place marker by three nullary planning fluents , meaning that zero, one or two items are aboard. Initially only is true. Exactly one of these facts is maintained. No additional object constants are needed.
For compactness, define the common loading preconditions
and common unloading preconditions
The four STRIPS actions are
Here the first unloading removes one of two items, and the last unloading removes the sole remaining item; items do not require fixed seat identities. The movement action remains as repaired in part (a) and changes none of the occupancy facts.
The planning state invariant is true exactly when items are aboard. Every action changes the marker by the same amount as the actual onboard count, so it follows by mathematical induction from the initial empty boat. In particular, a third load is impossible.
For , execute
and, if , append before the next iteration.
Each load starts with an empty boat beside an undelivered item. Each unload leaves that item west and restores the loading precondition. By mathematical induction on , after iteration the first items are west and the remaining items are east. Thus the automated planning goal holds after crossings and actions for . For , the empty plan already achieves the goal.
Use the STRIPS action
The onboard precondition prevents inventing an item at a bank, and deleting preserves the item's unique location. Restoring preserves the one-item planning state invariant.
The automated planning goal is the conjunction of the delivered-item facts:
The boat need not separately be constrained to end west, although any successful plan with must bring the final item there before unloading it.
In STRIPS, a state records the true ground facts; under the closed-world assumption, an absent fact is false. An action with positive preconditions , add effects and delete effects applies when , producing .
The given movement action adds the destination fact without deleting the old boat location. After its first crossing the boat can therefore be recorded at both banks, allowing physically impossible loading. Its source-bank symbol is also not a declared action parameter. Repair both issues by using the fully parameterized STRIPS action
Here excludes a vacuous same-bank crossing. The two static inequality facts already supplied suffice.
The given loading action has no capacity check. Consecutive loads can put arbitrarily many items aboard. Introduce a nullary planning fluent , true initially, and repair loading to
Unloading must restore , as in part (c). Including the bank explicitly as an action parameter removes the other unbound action variable. Equivalently, instantiate separate east-bank and west-bank actions.
These repairs establish the planning state invariants that the boat is at exactly one bank, each item is either at one bank or aboard, and at most one item is aboard. The first two hold initially and are preserved by deleting the former location when adding the new one; the capacity marker permits loading only when no item is aboard. Grounding implicit location variables alone would not repair the missing delete effect or the missing capacity check.
Depth-first tree search is complete under the stated initial reachability assumption, but is not bonus-optimal.
Let be the graph distance between fox and rabbit after round , with their initial graph distance. Initial reachability makes finite, and ordinary moves preserve membership in their common connected component of a graph. After the rabbit's next move, the triangle inequality gives intermediate separation at most . If that separation is at most two, the fox catches the rabbit that round. Otherwise the fox takes two steps along a shortest path, leaving
Thus a successful surviving history has at most rounds; if it does not escape by then, the next round captures it. The shortest-path pursuit distance bound excludes infinite live branches, even when the rabbit stays. Together with the finite branching factor, it makes the whole relevant search tree finite, so depth-first tree search eventually finds an escape whenever one exists.
For nonoptimality, take the corridor of part (g) and let depth-first tree search try left first. It immediately returns the one-round escape with bonus , whereas trying right twice earns . The decreasing separation proves termination, not optimality of the first returned escape.
Breadth-first tree search is complete and is still not bonus-optimal. Fix any deterministic rule for choosing among equally short fox routes; the completeness argument again uses only the finite branching factor. The unobstructed corridor of part (g) has unique shortest paths, so its fox moves are exactly the same under the new strategy. The one-round bonus is and the two-round bonus is , proving nonoptimality without any tie-breaking ambiguity.
If there is no route between fox and rabbit, the printed shortest-path rule needs a convention; letting the fox stay supplies a natural extension. The completeness argument is unchanged, and the counterexample above uses only connected squares. When the fox and rabbit initially belong to the same connected component of a graph, the shortest-path pursuit distance bound also makes every surviving branch finite. That additional property does not make the first escape maximize its bonus.
Breadth-first tree search remains complete but is not optimal for maximizing the bonus. Completeness depends on the finite branching factor and a finite successful depth, not on the objective used to compare escapes.
Use the one-row, seven-square example from part (e). The one-round escape at column leaves the fox at column , so its graph distance to the exit, and hence the bonus, is . The two-round escape at column leaves the fox at column , giving bonus . The earliest successful node therefore has bonus when bonus is achievable. Breadth-first tree search orders by rounds rather than terminal graph distance.
Ignore the fox and obstacles when estimating the remaining number of rabbit moves. Define the heuristic function
This is Manhattan distance to the nearest exit, a relaxation heuristic. Assume at least one exit; with none the instance is immediately unsolvable. The estimate is generally nonconstant and is not the perfect escape cost: obstacles can force detours, while pursuit can make an apparently nearby exit unreachable.
To prove it is a consistent heuristic, consider a surviving one-round transition from to . Let attain the minimum defining . The triangle inequality for Manhattan distance and the rabbit's move bound give
Every successful terminal state has . This proves consistency with unit round costs; summing the inequality along any successful route also proves that it is an admissible heuristic. Failed transitions need no successor estimate because they are discarded.
Depth-first tree search is neither complete nor optimal for minimizing rounds.
For incompleteness, use the two-row, three-column board from part (c), with exit . If stay is the first action explored, depth-first tree search follows the repeating state forever. Moving the rabbit down instead survives the round: under legal horizontal-then-vertical movement the fox moves to and then , leaving the rabbit safely at the exit. Thus a one-round escape exists but is never reached in this action order.
For nonoptimality, use an unobstructed one-row board with columns , initial fox column , initial rabbit column , and exits at columns and . Moving left once escapes at column with the fox at column . Moving right twice escapes at column with successive fox positions . A depth-first tree search that explores the latter route first returns two rounds although one suffices. This counterexample supplies an actual returned, suboptimal escape independently of the infinite-branch example.
Breadth-first tree search is complete and optimal for minimizing rounds. If a successful escape has finite length , there are only finitely many nodes at depths below , since the branching factor is at most five. Breadth-first tree search therefore reaches a shallowest successful node after finite work, even if other branches continue forever.
It is an optimal search algorithm because every search transition model step costs one round, so minimum depth is exactly the desired minimum number of rounds. The goal test must be applied to the surviving complete-round successor. Here a complete search algorithm guarantees finding an escape when one exists; it need not terminate on every unsolvable instance.
The branching factor of the search tree is at most five, so through depth it has at most
nodes in Big O notation. With no depth bound, the search tree can be infinite, despite the finite state space: tree search retains different action histories even when they end at the same position pair.
For a concrete repeating history, use a two-row, three-column board, indexed from zero, with the sole obstacle , rabbit at and fox at . Repeated rabbit stays leave the fox blocked horizontally with no vertical separation to reduce. Hence the same live state can repeat forever. An exit at is nevertheless safely reachable in one round.
Write . The ordered position pairs give at most states, or live states after excluding capture. Thus the usual Big O notation estimate is . An additional terminal-failure marker changes this by only one.
For distinguishable foxes, retain . Different foxes may share a square; none may share the rabbit's square in a live state. There are at most live position tuples, giving . These counts describe possible encodings; obstacles, starting positions and the fixed fox rule can make the reachable state space much smaller.
Let be the traversable squares and the exits. Sample the state space at the end of each complete round, so a live state is with . The given starting positions specify the initial state. The board and exits are fixed problem data, rather than changing components of the state space.
The rabbit has at most five actions: stay or move to one of its traversable orthogonally adjacent squares. A search transition model first applies that action, giving , and immediately checks for capture at . Otherwise hold fixed and apply the fox rule twice, checking for capture after each step. A capture is terminal failure; it must not be overlooked merely because the fox could subsequently move elsewhere. A surviving successor is . Equivalently, omit actions whose complete-round outcome is capture.
The goal test is the rabbit is on an exit after surviving the fox's entire turn: and no capture occurred in that round. Merely entering an exit before the fox moves is insufficient. Each surviving search transition model step has cost one when minimizing rounds.
Only legal moves are considered when applying the stated horizontal preference: try a legal horizontal step that reduces horizontal separation, otherwise a legal vertical step that reduces vertical separation, otherwise stay. If a blocked preferred direction is instead interpreted as forcing a stay immediately, the counterexamples below and all completeness and optimality conclusions remain valid.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact