1Introduction
A recipient borrows a serving dish when accepting food brought in it. Washing the dish and returning it satisfies the owner’s claim to the object. In the conventions considered here, the recipient also owes a gesture of return, usually food presented in the same dish. When that presentation counts as a gift, the original owner receives the dish and incurs the corresponding obligation. The dish is already home. The plan has another step.
We study a small family of return rules extracted as executable predicates from descriptions of reciprocal service (Orellana Sieder and Hult, 2019; Dameri and Audenot, 2021). The unit under study is the return convention. The rules are inputs, and a violation is a disagreement with an input rule. For the simplest convention, we prove that the number of outstanding gestures stays constant over all permitted handoffs. We use that condition to remove search branches that have lost access to release. For the stochastic part of the model, an authorization action exposes information about the other party’s willingness to close. The policy has to reserve a subsequent visit for the physical return. A late authorization can arrive after the last visit it could have authorized.
2Related work
2.1Representation and search
The distinction between an action precondition and a persistent fluent follows STRIPS (Fikes and Nilsson, 1971). A return can have one delete effect and one add effect on the same kind of fluent. In our domain the arguments of those effects are reversed, so merging them as a net zero edit to custody discards information. For temporal control we use availability windows over discrete events. Allen’s interval relations (Allen, 1983) can express finer scheduling constraints. We use only precedence and co-occurrence, which also lets us compile most conventions into the state-dependent operators described by Ghallab et al. (2004). The clock-dependent release rule is explicit in that compilation. Temporal search control (Bacchus and Kabanza, 2000) would be a natural way to specify prohibitions involving an entire sequence of solicitations.
Classical heuristic search over a projection is inexpensive (Bonet and Geffner, 2001), and delete-relaxation heuristics (Hoffmann and Nebel, 2001) are particularly good at finding the next meeting that both parties can attend. The relaxation admits plans that keep the dish at two addresses at once and plans that still own a signed release after it has expired. Strong cyclic planning allows a fair nondeterministic loop with a possible exit (Cimatti et al., 2003). Here the outcome of the next inquiry depends on an unchanging disposition and a changing calendar. Treating a standing refusal as a repeatable draw from a fair outcome set can certify a policy that will leave the same dish outstanding for every remaining step. Žuvela and Vind (2020) found a related dependence when evaluating repeated requests for confirmation of whether a loan was permanent.
2.2Planning under incomplete information
Our observation kernel makes a subproblem a mixed-observability POMDP (Kaelbling et al., 1998). The finite-horizon objective follows the backward induction of Smallwood and Sondik (1973). We use a loss for leaving debt outstanding at the deadline and a per-step cost. An undiscounted shortest-path formulation would require care about improper policies (Bertsekas and Tsitsiklis, 1991). Under compulsory refill there is no proper policy from a nonempty ledger. In domestic restoration tasks, earlier simulators assign an end-of-episode reward when every object is at its recorded home (Avero and Diko, 2021; Leitão and Bregger, 2023). Reversal of a debt has no effect on that reward. Sereke and Nolet (2022) distinguish acknowledgment of an object from acknowledgment of an accompanying contribution. Their physical-return benchmarks record both, though they end each episode after the first admitted transfer.
3Domain and observability
3.1Ledger
Let be the owner of dish and its current possessor. The two roles are properties of the object and the execution, respectively. A directed token says that owes a gesture on account of . A token never serves as authority to change the owner field. At initialization the gift has already been accepted, the receiving party holds the object, and one token exists per active dish. An unfilled transfer requires authorization for the return to the owner. Tokens stay in the ledger until consumed by a handoff. A signed permission changes what is legal at a meeting, with no immediate change to the ledger.
In the one-dish fragment a filled handoff consumes and adds . The new debtor also takes custody. For the purposes of this fragment an item is filled if the receiver counts its contents as a gift, even if no new food was prepared. Reclassifying a gift after the exchange is outside the domain. A permitted unfilled handoff consumes the token and leaves . If is a borrower the operator also places the object in the owner’s custody, within the same meeting, when the owner is present and the contract permits direct return. The planner can solicit permission for that three-party handoff. For a single pair, a release that would deliver an object away from its owner is unavailable. For a two-person return this restriction blocks release after an odd number of filled handoffs.
Let be the set of dishes and the outstanding tokens after transition . The end test given to the evaluator is
3.2Invariant under refill
Let count tokens consumed by executed action and count tokens created. We count creation events even when the new token has the same arguments as a previously resolved token. By construction,
Proposition 1 (Closed refill rules). Suppose and each available action that consumes a token creates at least as many tokens. Then no finite execution achieves Eq. (1).
Proof. For transitions that consume a token, the hypothesis gives . For all others and . Summing Eq. (2) gives at every finite . Apply Eq. (1).∎
When meetings remain available, one filled handoff restores custody in the two-person, one-dish case. Another restores the initial ledger and replaces the dish at the borrower’s address. On a repeating calendar even the augmented state repeats if the next available meeting is indexed modulo the calendar period. In the lifted representation the two most recent gifts have different event identifiers. Those identifiers may be ignored for reachability. They may not be ignored for costing, since the policy pays for each gift regardless of which direction it went.
3.3Requests and release
The domain has two request channels. A private inquiry produces either an indication of willingness or an indication of refusal. It grants no action permission. A formal request can produce a signed ticket for the next valid visit or a refusal. The ticket identifies the dish, its final owner, its current possessor and the visit slot. A signed ticket satisfies the release precondition only for the named exchange. The planner can leave it unused. It cannot be spent early on a different visit or used twice. The rule compiler rejects tickets for visits with incompatible custody requirements, even when the named people are all free.
Each pair has a latent disposition sampled once, with three classes. An unconditional class accepts formal requests for a feasible return slot. A calendar-dependent class accepts them when the occasion meets the active rule’s predicate. A continuing class declines. These are deterministic conditions on the formal action and latent state. The private inquiry is noisy conditional on and the occasion family. At the default prototype it returns a positive sign with probabilities 0.85, 0.60 and 0.15, respectively. Rule templates draw perturbations of at most 0.05 per row. A group extending the private reply without extending the validity of its tickets changes two rows of the observation kernel and no row of the transition kernel. We ablate the private channel in Section 6.3.
Time is public. A wait action advances to the next calendar slot, and every other action advances by one slot after it is processed. Speaking slots and transfer slots can overlap. Because each step holds one action, asking for a release during a transfer slot forfeits the transfer at that slot. Each feasible successor is computed after expiring all permission records dated earlier than the new time. Expiration is independent of whether the planner has a later return scheduled.
4Planning
Write for the public state, including the ledger and the remaining calendar, and for the posterior over dispositions. The formal response is observable. Given response to action , the update is
We use the exact posterior at the current public state as the key, with the remaining horizon, in a memoized dynamic program. All probabilities are rational and are stored as reduced integers during planning. We choose a cost of 1 per executed action, an additional cost of 2 per filled transfer, and a terminal cost of 32 for an open case. The first two costs describe event counts, with a premium for producing a gift. A demand to minimize gifts alone admits a policy that waits until time runs out. Under the stated costs a policy is allowed to stop early and take the penalty if the reachable closure probability is too low. Illegal actions are masked in the ledger-aware variants.
If is one-step cost and the public successor, the full search uses
Terminal goals have value zero for every horizon, and for other states. Actions restricted by a valid ticket are generated before Eq. (3) is called. The sum includes all observable outcomes of actions with nonzero probability. In Algorithm 1 the certificate check first ignores all private replies and sets each formal reply optimistically to acceptance wherever some element of posterior support permits it. It searches this finite relaxed graph for a goal within the remaining time. For the closed refill fragment Proposition 1 proves the same result without building the graph. The relaxed test can underestimate the cost of successful closure. It cannot remove a state from which a legal closure is reachable within the horizon.
5Evaluation design
5.1Instance construction
We generated 600 independent rule families. A family fixes a rule graph, availability mask, observation-noise range and ownership pattern. Four start cases per family vary the initial slot and draw latent dispositions from the family’s prior. Cases in a family share their rule graph and public time grid. We assigned 300 families to development, 100 to validation and 200 to the test set before generating the four cases. The test set has 50 families of each of four kinds. A rule family’s salted identifier fixes its split, and a separate stream keyed by the instance identifier drives observation outcomes. We fixed tie breaks, cost weights and the 12-slot horizon before the test runs. Appendix A describes the split and the random streams. Test-time priors are provided to every belief-based policy. Outcome draws for a given action, state and visit are coupled across policies; alternate visits receive their own draws. The random seed never enters a policy state.
The four case kinds appear in Table 1. In the ordinary case, a pair with one dish has periodic meetings that can support release. In the calendar case, the release is tied to one marked visit in a shorter window. The pair may receive two independently owed dishes in the nested case. The outer dish can contain the inner dish during transfer, and custody records refer to each dish separately. A formal request for the inner return may name a visit that satisfies the calendar predicate for a pending outer gift. That visit also turns on the corresponding refill operator, even for a party that could previously perform only an empty transfer at that address. In the inherited case some admissible signatures bind a previous owner’s availability pattern and some bind the active owner. Present ownership is always public. Inheritance is a stored rule on a particular dish, not something inferred from a family name.
| Rule family | Dishes | Starts | Closures | Rate (%) |
|---|---|---|---|---|
| Ordinary | 1 | 200 | 190 | 95.0 |
| Calendar | 1 | 200 | 183 | 91.5 |
| Nested | 2 | 200 | 172 | 86.0 |
| Inherited | 1 | 200 | 147 | 73.5 |
| All | 800 | 692 | 86.5 |
5.2Comparators and inference
Inventory A* uses a cost of one per step with an admissible lower bound given by the number of needed deliveries divided by the maximum dishes delivered at a visit. It commits to an empty return because the added gift premium makes a filled handoff strictly more expensive for the same delivered custody. Refill only excludes all release actions and executes the earliest permitted filled return when custody is wrong. If custody has been restored it stops. Myopic release scores each request by its predicted acceptance and the earliest compatible delivery. If no request can secure a ticket for an upcoming visit, it falls back to the next feasible filled return that restores custody. MAP replanning solves the deterministic problem for the posterior mode at each step and masks returns for which it lacks an actual signed ticket. The disposition oracle uses the same cost and exact search after receiving . It still needs a signed ticket. Informing the oracle about existing permissions alone would add no information, since all policies can read their own records.
The primary estimand is the test-family mean paired difference in valid closure probability between full search and MAP replanning. A valid closure occurs when all actions pass replay and the first occurs by slot 12. Early stops with open debt, and planned actions rejected by replay, count as failures. We report percentile intervals from 10,000 bootstrap replicates of families within each case kind (Efron and Tibshirani, 1993). Within each replicate we keep the two policies paired on each start. Resampling individuals would split cases that share their availability masks. Comparisons beyond the primary contrast are descriptive. The terminal-cost ablation reuses the same event streams.
6Results
6.1Completion and possession
The inventory-only plan returns all objects in 782 cases in its projected simulator, which accepts physically feasible handoffs without reading the ledger. In the full domain those 782 plans attempt an unlicensed transfer, and the other 18 never find a delivery slot. The refill policy has lower physical recovery and zero closure. Table 2 gives counts, and Figure 1 displays the gap on the proportion scale. The three release policies and the oracle have identical admissibility masks. Their differences reflect which visits and outcomes they make reachable. The oracle has the highest observed completion and should be read as a comparator supplied with privileged information, not a pointwise upper bound on success. It minimizes expected cost under Eq. (4), which allows early stopping.
| Planner | Custody restored | Valid closures | Closure (%) | Open or invalid |
|---|---|---|---|---|
| Inventory A* | 782 | 0 | 0.0 | 800 |
| Refill only | 761 | 0 | 0.0 | 800 |
| Myopic release | 671 | 600 | 75.0 | 200 |
| MAP replanning | 693 | 620 | 77.5 | 180 |
| Full search | 734 | 692 | 86.5 | 108 |
| Disposition oracle | 755 | 724 | 90.5 | 76 |
The paired difference against MAP replanning is 9.0 points (95% interval 5.5 to 12.6). Full search finds a productive solicitation in some cases where the modal type is continuing. The same solicitation can be worth the slot when the posterior puts its remaining mass on a calendar-dependent type and the only qualifying visit is two slots away. Conversely, for a pair whose unconditional class is modal only until the first private inquiry, a plan that spends the speaking slot on a formal request can leave too little time to act on the refusal it obtains. The main difference in the logs is the placement of the first formal request. In a paired audit of the 72 net additional closures, there were 103 cases closed by full search alone and 31 closed by MAP alone. Several of the latter had a substantially lower posterior closure probability than typical cases at initialization. The cost criterion permits declining such a case even when its sampled disposition would have allowed closure.
6.2When the projected plan ends
Figure 2 gives cumulative completion under the fixed 12-slot policy, rather than results from solving a different instance at each horizon. At slot four, 286 valid closures have occurred. The inventory policy has restored 708 projected inventories by that slot. A success metric triggered by the last reduction in physical distance would therefore put the inventory planner well ahead early in the episode. The gap peaks at 422 cases at slot four on this grid.
We traced the 108 failures of full search to the first event that made closure impossible or to a voluntary halt while closure still had positive probability. The resulting categories are mutually exclusive. A refusal that revealed the continuing type accounted for 47, expiration of the last feasible visit for 39, and a positive-cost voluntary halt for 22. The first two categories use the latent-state replay when assigning cause. In the third category the halt precedes the deadline, and an alternative allowed policy would have a positive probability of closing from the public state. An oracle cannot necessarily change the first category. It can change some calendar expirations by asking for the appropriate recipient’s signature before the other party has responded.
Figure 3 shows the classification by case kind. The inherited failure rate includes both continuing-type cases and brittle calendars that no longer agree with current possession. In 16 of the 53 inherited failures the last possible slot was an occasion attached to the past owner. Six of those slots had already elapsed before the dish was actually returned to the active owner with a gift. At that point the new obligation was attached to a valid owner and an appointment that could only occur in the past.
6.3Policy ablations
Removing the private channel costs 26 closures. Raising the terminal cost to 64 recovers ten at the expense of increasing the mean executed actions per start from 6.1 to 6.7. The search pursues favorable replies with low prior probability when the cost of stopping rises. A third ablation lets a ticket name two successive visit slots while still requiring all relevant parties to accept it. Only the nested family has a second physically feasible visit. Table 3 includes this result as a change to the legal execution set.
| Setting | Closures | Difference |
|---|---|---|
| Full search | 692 | 0 |
| No private channel | 666 | −26 |
| Terminal cost 64 | 702 | +10 |
| Extended nested ticket | 705 | +13 |
7Nested transfers and accumulated precedent
A plate can travel on a tray. The physical movement of the plate then requires custody of both items, even if the tray remains an independent loan. Benarroch and Kvasný (2024) reports that borrowers sometimes present the small container already sitting inside the larger one when the recipient agreed to receive only the small container. We introduce a variant with an explicit support constraint. An inner dish may be handed over by itself when it has been removed beforehand. Removal occupies a slot. A gift on the tray counts against the tray’s own token. An outer token is therefore resolvable with an unfilled handoff only if the tray reaches its owner without a departure gift, including a filled inner dish resting on it.
We instrumented 60 separately generated nested instances with a side rule for acknowledgments (Fraser and Caras, 2022). The recipient at the designated release visit can sign a receipt and send it back in a small envelope. A receipt in the recipient’s hand creates nothing. A receipt presented on the outer tray counts as a contribution under the active outer rule. We varied that routing bit while holding the signature, container state and visit constant. A valid policy closed 49 of 60 starts when the receipt was handed over separately and 32 of 60 when it traveled on the tray. On replay, 18 starts closed only under separate routing and one only under tray routing. The exceptional case with tray routing uses a new outer token to schedule a visit the original release did not make available. The class is small enough that we report counts without using it in the primary inference.
The episode that motivated this extension began with a cake plate placed on a borrowed tray. The designated return visit accepted the empty tray. The acknowledgment for receiving it was handed back on the now-empty tray. From the viewpoint of the acknowledgment rule the recipient had just received a signed document as a presented object and owed a gesture. The owner lent out the tray again to carry the acknowledgment home. By Eq. (2) the two-document variant cannot terminate if each acknowledgment subsequently travels on an object whose rule treats it as a contribution. The physical size of the acknowledgment is absent from the proof. Printing it smaller helps only on instances whose support rule admits a different carrier.
8Scope and conclusion
The generator takes return conventions as fixed for an episode. A recipient can decline a release, but cannot stop counting deliveries halfway through unless the template admits that transition. The fractions above quantify solver performance under those inputs. No prevalence estimate for any disposition follows from them. Established relations may also share a release across multiple objects. The two-dish model with one ticket per dish has no such global release. Adding the operator would require a joint authorization state when the people who own the dishes differ. Matsuzaki and Bile (2023) describes that case for organized lending, where a local custodian signs for a collection under a shared rule.
AGenerator and implementation
Each rule family has one of four topology codes, its sequence of 12 availability masks and a latent-type prior tabulated in twentieths. The generator draws at least two feasible visit masks per actor before applying the template restrictions. A latent draw uses integers from a counter-based stream; observation thresholds use hundredths and the same stream with a separately keyed counter. Calendar masks for development and validation can have the same Hamming weight as test masks. They cannot have the same generator template identifier. Split assignment is stratified by topology. We canonicalize actor labels before generating test ids to keep relabelings of a single case together. Multiple starts per family are retained when their realized dispositions or starting times coincide. There is no case-wise deduplication after the split.
BSearch cost and reproducibility
We checked the relaxed certificate by disabling it on the validation set and comparing the selected action and value at every start. Search tables are process-local and discarded between starts. At the main horizon the median end-to-end full-search time per case was 8.4 ms, and the 95th percentile was 62 ms, on one 3.2 GHz x86-64 CPU core. These timings include the reachability precheck and exclude replay. Search evaluates up to five action schemas per slot in the core generator, with grounded arguments generating additional branches in two-dish cases. Peak resident memory for a single sequential test sweep was 74 MB. The inner receipt extension runs independently with the same state representation and a routing bit in the operator input. No learned model or accelerator is used.
Acknowledgments
We thank Flóra Eszenyi for independently implementing the transfer replay and Márcio D. Calvetti for identifying the support constraint in the two-dish generator.