cross(X) requires person(X) costs WX where walk(X, WX).

crossTogether(X, Y) requires person(X), person(Y), X < Y
costs Wmax where walk(X, WX), walk(Y, WY), max(WX, WY, Wmax).

The declaration of takeLamp remains unchanged, as the time to hand over the lamp is negligible.

Using this modified planning domain, the 5-step plan reported in Section 2.1 has cost 19. Actually, it is optimal for plan length l = 5. However, when we relinquish the first intuition that the fastest person, joe, always has the lamp and consider the problem under varying plan length, then we can find the following 7-step plan:
P = h {crossTogether(joe, jack)}, {cross(joe)}, {takeLamp(william)},
{crossTogether(william, averell)}, {takeLamp(jack)}, {cross(jack)}, {crossTogether(joe, jack)} i Here, costP(P**) = 17**, and thus P is admissible with respect to cost 17. This means that the Quick Bridge Crossing Problem has a positive answer. In fact, P has least cost over all plans of length l = 7, and is thus an optimal 7-step plan. Moreover, P has also least cost over all plans that emerge if we consider all plan lengths. Thus, P is an optimal solution for the Quick Bridge Crossing Problem under arbitrary plan length.

## 3.4 Bridge Crossing Under Incomplete Knowledge

The language K is well-suited to model problems which involve uncertainty such as incomplete initial states or non-deterministic action effects at a qualitative level. The enriched language Kc gracefully extends to secure (conformant) plans as well, which must reach the goal under all circumstances (Eiter et al., 2000b, 2003b). More precisely, an optimistic plan hA1**, . . . , A**ni is *secure*,
if it is applicable under any evolution of the system: starting from any legal initial state s0, the first action set A1 (for plan length l ≥ 1) can always be executed (i.e., some legal transition hs0, A1, s1i exists), and for every such possible state s1, the next action set A2 can be executed etc., and after having performed all actions, the goal is always accomplished (cf. Appendix for a formal definition).

While secure plans inherit costs from optimistic plans, there are different possibilities to define optimality of secure plans. We may consider a secure plan as optimal, if it has least cost either
- among all optimistic plans, or
- among all secure plans only.

In the first alternative, there might be planning problems which have secure plans, but no optimal secure plans. For this reason, the second alternative appears to be more appropriate.

Definition 3.6 *A secure plan* P is optimal for a planning problem P*, if it has least cost among all* secure plans for P*, i.e.,* costP(P) ≤ **cost**P(P
′) *for each secure plan* P
′for P*. The* secure cost of P*, denoted* **cost**∗
sec(P)*, is* **cost**∗
sec(P) = **cost**P(P
∗)*, where* P
∗*is any optimal secure plan for* P.

The notion of admissible secure plans is defined analogously.

For example, assume that it is known that at least one person in the bridge scenario has a lamp, but that neither the exact number of lamps nor the allocation of lamps to persons is known. If the four desperate persons now ask for a plan which brings them safely across the bridge, we need a
(fast) secure plan that works under all possible initial situations. In Kc, this can be modeled by replacing the initially-part with the following declarations: