River Crossing
Task
A farmer has five animals on one side. He needs to get all animals to the other side of the river. Unfortunately, he only has two spaces available on his boat and some animals cannot be left on their own. Find a series of boat crossings to get all animals to the other side.
Animals
- 2 Wolves
- 1 Fox
- 1 Chicken
- 1 Worm
Constraints
- Wolves eat foxes.
- Wolves eat chickens.
- Foxes eat chickens.
- Chickens eat worms.
Solution
The problem is solved using Answer Set Planning in
DLV with the planning
frontend. The planning frontend can be invoked with the -FP switch.
The command to run the solver is
dlv -FP -n=1 -stats -planlength=7 -planminactions=1 -planmaxactions=1 crossing.plan crossing.bk
STATE 0: boat_here, here(wolf1), here(wolf2), here(fox), here(chicken), here(worm)
ACTIONS: crossTogether(chicken,fox)
STATE 1: here(wolf1), here(wolf2), -here(fox), -here(chicken), here(worm), -boat_here
ACTIONS: cross(fox)
STATE 2: here(wolf1), here(wolf2), here(fox), -here(chicken), here(worm), boat_here
ACTIONS: crossTogether(fox,worm)
STATE 3: here(wolf1), here(wolf2), -here(fox), -here(chicken), -here(worm), -boat_here
ACTIONS: cross(chicken)
STATE 4: here(wolf1), here(wolf2), -here(fox), here(chicken), -here(worm), boat_here
ACTIONS: crossTogether(wolf1,wolf2)
STATE 5: -here(wolf1), -here(wolf2), -here(fox), here(chicken), -here(worm), -boat_here
ACTIONS: cross(fox)
STATE 6: -here(wolf1), -here(wolf2), here(fox), here(chicken), -here(worm), boat_here
ACTIONS: crossTogether(chicken,fox)
STATE 7: -here(wolf1), -here(wolf2), -here(fox), -here(chicken), -here(worm), -boat_here
PLAN: crossTogether(chicken,fox); cross(fox); crossTogether(fox,worm); cross(chicken); crossTogether(wolf1,wolf2); cross(fox); crossTogether(chicken,fox)