Q3.Solving a Planning Problem with Prolog
The Frog and Toad Problem
For this question, you will complete the coding of a Prolog program, which uses Prolog’s search capabilities to find the solution to a well known puzzle. The puzzle goes as follows:
Three frogs and three toads are lined up in the configuration illustrated in the Starting State figure below. The frogs are on the right and the toads on the left.
Frog and Toad Puzzle Start State
By a series of valid amphibian moves you must transform the state to the Goal state, also illustrated below.
Frog and Toad Puzzle Goal State
The frogs and toads can only move in accordance with the following specification:
· Only one amphibian (either a frog or a toad) can move at a time.
· Frogs can only move to the left.
· toads can only move to the right.
· Each move is ether a crawl or a hop.
· A crawl is a move to an adjacent empty space.
· A hop is a move to an empty space that is two spaces away from the starting space, such that the space between the start and end of the hop is occupied by another amphibian (frog or toad).
· Frogs can only hop over toads and toads can only hop over frogs.
To solve this puzzle, you should use the bb_planner.pl Prolog program. In order to configure it to solve this particular problem you will need to define the predicates initial_state, goal_state and transition.
Code Resources and Solution File Template
As a starting point for answering this question, three program files are provided on the SWISH Prolog system. These are
· bb_planner.pl
· Link: https://swish.swi-prolog.org/p/bb_planner.pl This Prolog program implements a simple breadth-first planner program.
· bb_jugs.pl
· Link: https://swish.swi-prolog.org/p/bb_jugs.pl This is an example file, which illustrates the use of bb_planner to solve a simple puzzle.
· frog+toad_template.pl
· Link: https://swish.swi-prolog.org/p/bb_frog+toad_template.pl
This is a template for you answer file.
You should copy it by selecting “Save” from the File menu. Then rename it by entering a new name, which should be username_frog+toad.pl where username is your actual username. Then press the Fork button on the right of the name entry box. Then press the Fork Program button at the bottom of the dialogue window.
State Representation
Before completing the program, you will first need to work out a representation for possible states that the frogs and toads can be in during the movement sequence. There are various ways that you could do this, but probably best to use something simiple as long as it is sufficient to hold the information required to specify any state that could arise.
Coding the Required Predicates
Once you have decided on your state representation, you need to code the initial_state, goal_state and transition, replacing the examples in the template file. For a successful result you need to ensure that your transitions cover all the possible moves that can be made by any amphibian in any possible state. You will paste your solutions in the entry boxes of the following sub-questions.
Running Your Program to Solve the Problem
Once you have coded the predicates you can try running the find_solution predicate. If you have defined the problem in a viable way, this should generate a sequence of moves that solves the puzzle.
Q3.1 initial_state
Copy your Prolog code specifying the initial_state predicate into the box below:
Q3.2 ‘goal_state’ predicate definition
Copy your Prolog code specifying the goal_state predicate into the box below:
Q3.3 ‘transition’ predicate definition
Copy your Prolog code specifying the transition predicate into the box below:
Q3.4 The Solution
Run the find_solution predicate to find a valid sequence of moves from the starting state to the goal state. If this works, copy the plan that is produced into the box below: