The paper locates Picat in a long line from PLANNER and Prolog to tabled logic programming. A planner can be written recursively: if the current state is final, return an empty plan; otherwise choose an action, recurse from its successor and prepend the action. The specification is compact, but unrestricted backtracking may traverse cycles and re-expand converging paths indefinitely.

Tabling caches selected calls and answers. In a state-space search, the table is analogous to state marking: a call for a state can reuse an answer or failure computed earlier. This changes recursive logic programming from an unremembering tree walk into a search over an implicit graph. Cycles require fixed-point evaluation, but duplicate work becomes identifiable.

Picat combines logic variables, pattern matching and backtracking with arrays, maps, loops, functions, constraints and tabling. The planner module hides the table declarations from most users. A domain modeller supplies final/1 and action/4; built-ins perform unbounded, resource-bounded, iterative-deepening or branch-and-bound search.

The paper’s argument is not tabling alone. Planning performance depends on the identity of a state. Structured data can omit object names that make no difference, ordered lists can collapse permutations, hash-consing can share repeated subterms, action rules can commit when a choice is safe, and admissible estimates can reject paths whose remaining budget cannot cover the goal.

A predicate rule has a head, an optional condition and a body. With the backtrackable arrow, failure in the body returns control to the original call so another applicable rule can be tried. With the non-backtrackable arrow, the remaining rules are discarded for that call. Functions use non-backtrackable rules.

This distinction matters in action generation. Most planning actions are nondeterministic choices: several moves may be applicable and must remain available to search. A rule that deterministically unloads a package already at its destination, however, can safely commit if domain knowledge proves that postponing it cannot improve an optimal plan.

Pattern matching can destructure a state directly. An as-pattern simultaneously binds the whole structure and its components. Loops and list comprehensions make conditions such as “every truck is empty” readable. Arrays support indexed configurations; ordered lists support canonical multisets. A dollar prefix ensures that a structure in an argument is treated as data rather than a function call.

Picat is dynamically typed and multi-paradigm. The paper focuses on the planner and tabling, not on a claim that one purity discipline governs every construct. Imperative updates, constraint modules and logic variables coexist. Operational choices are explicit enough for a modeller to affect search without writing a planner from scratch.

The declaration table (+,-,min) treats the state as input, the path as output and cost as a minimised answer. When a call repeats with the same input state, the table can supply or refine its stored result. An nt mode excludes an argument from variant checking and answer storage where the planner needs inherited data to flow without changing call identity.

The generic path relation has a final-state rule returning empty path and zero cost. Its recursive rule selects an action, obtains a path from the successor, prepends the action and adds costs. On an acyclic graph, a first answer may later be replaced by a cheaper one. With cycles, linear tabling reevaluates calls until a fixed point is reached.

The paper’s directed acyclic graph yields this replacement visibly. Search first follows a→b→c→d at cost eight and tables it for a. Backtracking later tries a→c→d at cost five. Because the cost argument uses min, the shorter answer replaces the longer one and becomes final.

The comparison with Dijkstra is precise but limited. For a single-source shortest-path problem, linear tabling resembles Dijkstra while storing shortest continuations from encountered states to the goal rather than distances from the source to every encountered state. It remains a logic-program evaluation strategy, not a textual implementation of Dijkstra.

final(S) recognises a goal state. action(S,NextS,Action,ACost) enumerates legal transitions, returns a successor and a non-negative cost, and names the chosen action. If only length matters, each action costs one. Rule order affects the search order, while committed rules can suppress later alternatives.

best_plan_unbounded performs depth-unbounded tabled search and then compares the found optimum with a supplied limit. Once a state fails, it is not explored again. This is suitable where dead ends are useful and an external resource horizon is unnecessary.

plan performs resource-bounded search. best_plan repeatedly invokes it from an initial limit of zero, relaxing the limit until a plan is found. Unlike ordinary IDA*, tabled information can survive the iterations. best_plan_bb first finds a plan, then imposes successively stricter limits until no better plan exists.

The function current_resource() reveals the remaining bound of the latest planner call. A domain model can compare it with an admissible estimate and fail early when the estimate exceeds the remaining resource. The implementation walks the call stack to find the relevant planner frame; this is a pragmatic interface between generic search and a domain heuristic.

The internal call carries an array containing remaining limit, reversed partial plan and accumulated cost. These values are passed as a non-tabled argument. Reaching a final state throws the reversed plan and cost as an exception, caught by the outer planner call. Otherwise an action produces a successor, its cost is subtracted and search continues only if the new limit is non-negative.

Suppose state S previously failed with R′ resource. A revisit S with R≤R′ cannot uncover a path that the stronger earlier budget missed, so it fails immediately. A revisit with R>R′ must be expanded because extra resource might make a continuation feasible. This is the exact resource monotonicity exploited by the table.

The scheme avoids a dangerous overgeneralisation. Recording only “S failed” would be unsound because S may fail under a tight budget and succeed under a larger one. Conversely, treating every pair (S,R) as unrelated would miss dominance between budgets and weaken reuse. The special treatment stores the best failed limit for the state.

Iterative deepening benefits because early rounds are not discarded. Failed-state bounds from limit two can prune equal or weaker occurrences in later searches while still permitting a state reached with a genuinely larger remainder. This differs from ordinary IDA*, whose next iteration starts afresh.

Transport represents a state as an array of ordered truck and waiting-package lists. A waiting package is a source–destination pair, not a named object. A truck is represented by location, an ordered list of carried destinations and capacity, not by its name. Packages with the same endpoints and trucks with the same operational attributes become indistinguishable.

This is symmetry breaking by representation. Two arrangements differing only by arbitrary labels map to one table key, so the planner explores them once. Ordered insertion keeps multisets canonical. The choice must preserve every feature that affects actions, costs or the goal; otherwise distinct planning states would be merged unsafely.

Hash-consing interns equal ground terms. Lists [1,2,3], [2,3] and [3] can share suffix nodes rather than duplicate them. Transport places a truck’s capacity last so trucks with the same capacity can share that tail. Term equality can then exploit pointer identity for shared structures, accelerating table lookup.

The memory trade-off is explicit. Picat avoids a prior global grounding that might explode, but it tables every encountered state. A poor representation can still consume substantial search memory. Canonical form, structural sharing and domain pruning are therefore not cosmetic coding preferences; they determine how much the table retains.

Transport translates load, unload and move operators into list selection and ordered insertion. A basic load remains nondeterministic. A complete model commits to unloading at a package’s destination. Its admissible estimate combines remaining load/unload operations with the maximum, over remaining packages, of a lower bound on transport cost using any truck.

Tetris represents squares, rectangles and L-shaped pieces in separate sorted lists. Actions update one selected piece and check occupancy. Its heuristic ignores interactions: estimate each piece’s shortest distance to the target region as if it were alone, then sum. Because ignoring obstacles cannot increase the true required work, the estimate is admissible, though conservative when pieces compete for target cells.

Floortile represents robot positions and painted white and black tiles. Changing colour can be joined to painting as a macro action. Generator-specific knowledge can make certain paint choices deterministic. The model uses depth-unbounded search: unreachable unpainted tiles naturally produce tabled dead ends, so no extra heuristic is required.

Parking stores each curb as a list of at most two cars, with the roadside car first because it can move without disturbing the curbside car. It includes the goal configuration in the state so action rules can detect correct placements. Domain rules commit moves into final positions and avoid moving a correctly placed car. Its heuristic counts incorrect cars, with stronger costs for reversed two-car configurations.

Picat-nt uses Prolog-style non-tabled iterative deepening with the same state representation. Picat-nh removes heuristics from the five domains that use them. Symba is the domain-independent bidirectional A* winner of the IPC’14 optimal sequential track. All compared solutions had the same plan quality where both planners solved the instance.

Across 171 listed instances, the table reports Picat solving 147, Picat-nt 73, Picat-nh 118 and Symba 87. Picat solved more instances than Picat-nt in every domain except Childsnack and Tetris; the non-tabled variant solved none in Barman, Cave, Floortile or Transport. In Parking, the heuristic-free version solved none compared with eleven for Picat.

Picat solved more listed instances than Symba in every domain except Floortile, where both solved twenty. The runs used a 2.4 GHz Intel i5 notebook with 4 GB RAM, g++ 4.8.3 and a 30-minute limit per instance. Total Picat runs finished within 24 hours; Symba’s took more than 72. The paper does not provide per-instance runtimes in this table.

The ablations support causal interpretation better than a bare cross-system comparison. Holding state representations similar while removing tabling isolates some effect of state memory. Removing heuristics from the relevant models isolates some effect of the lower bounds. Yet code paths and control details may still differ, and the nine domains do not constitute a timeless league table.

A state should contain enough information to determine legal successors, remaining costs and the goal, but no irrelevant labels or redundant permutations. Ordered collections create canonical keys. The placement of fields can improve suffix sharing. Arrays are used when indexed updates matter and list-tail sharing is unavailable.

Action definitions should make precondition checks and updates efficient. Standard list operations such as select, nth and ordered insertion simultaneously express and execute changes. Action order puts promising or forced moves first. Commitment should encode a proven dominance rule, not an intuition.

Domain knowledge can prune useless transitions, combine actions into macros and protect achieved subgoals. A lower-bound heuristic should be cheap enough to repay its cost and admissible enough to preserve optimum. The paper’s examples use simple knowledge intentionally, prioritising readability and avoiding a specialised solver disguised as a model.

Tabling makes these choices cumulative. If symmetric states remain distinct, each occupies memory and receives separate expansions. If an unsafe abstraction merges states with different futures, table reuse becomes unsound. If a heuristic is weak, many states survive each bound. The table does not repair a bad model; it amplifies the state equivalence the model declares.

Picat does not perform the prior grounding typical of many state-space planners, avoiding one source of memory explosion. Search can nevertheless be memory demanding because encountered states are tabled. The authors identify compact, efficient, shareable state structures as future work. Avoiding one bottleneck does not abolish space complexity.

The experiments cover deterministic sequential optimal domains with hand-written Picat models. They are strong evidence that tabling plus modelling was viable in the reported environment, not evidence about all planning formalisms, uncertain action models or modern systems. The comparative claims stay attached to nine domains, a 30-minute limit and specified hardware and compiler.

The authors suggest Picat as an implementation language for action languages such as A, Golog and K. Those languages conventionally use flat fact states and emphasise expressive modelling. An efficient translation would need to recover structural representation, symmetries, control knowledge and heuristics automatically. The paper presents this as a research direction, not a completed compiler.

The most durable idea is selective memory. A tabled state is a claim that every path arriving there shares the same remaining problem. A failed resource record adds a second claim: failure under a stronger budget dominates failure under weaker ones. Both claims are powerful because they are semantic assertions about equivalence and monotonicity, not merely caching tricks.