lisp人工智能AI代写 CSE2AIF Assignment 1

CSE2AIF – Artificial Intelligence Fundamentals 2018 Individual Assignment 1

Due Friday 31 August 2018, 10:00am

General Information

This assignment is to be done individually, and contributes 10% of your final mark for this subject. The submission date for the assignment is Friday 31st August 10:00am. Submission is electronic. Details of what to submit are provided below. Make sure that you follow the directions carefully and that the files are named exactly as specified in the instructions.

The assignment is to be done individually. This means that any code that you write must be your own. You must not collude with other students in any way, and you must not outsource your work to any third party. For information on plagiarism, see the La Trobe University policy on academic misconduct at http://www.latrobe.edu.au/students/learning/academic-integrity. Plagiarism is treated very seriously. Penalties will be applied and are strictly imposed.

Solving the Towers of Hanoi Problem using State Space Search

The Towers of Hanoi problem can be described as follows:

•   There are three pegs, labelled A, B, and C.
•   There are 3 disks on peg A. The top disk has a diameter of 1, the middle disk has a diameter of 2, and the bottom disk has a diameter of 3.
•   There are no disks on peg B or peg C.
•   You must move one disk at time and you cannot place a larger disk on top of a smaller disk.
•   The problem is to get all of the disks on peg C.

Initial State:

Goal State:

ABC

ABC

While various techniques can be used to solve this problem (recursion being the most popular), for this assignment you must use state space search. In Part A of this assignment you will write the basic Lisp code to solve this problem using breadth-first-search. In Part B you will extend this by including a heuristic, and solving the problem using a-star search.

Part A – Using breadth-first search State Representation:

A state is to be represented as a list of three (sub)lists – one for each peg. If a peg contains no disks, then the list for that peg is empty; otherwise the list contains a sequence of numbers that indicates which disks are on that peg, from top to bottom. Number 1 corresponds to the smallest disk; number 2 corresponds to the second smallest disk, and so on. Thus, for the Initial State shown above, the lists for pegs A, B and C are

respectively (1 2 3), (), and (). The start state is represented as the list containing these three lists; i.e., list ((1 2 3) () ()) .

Writing the code:

Work through the following:

1. Define a parameter *start-state*, whose value represents the initial state. Initialise it to the start state.

as the

2. Define a parameter *goal-state*, whose value represents the goal state. Initialise it to the goal state.
3. Write a lisp predicate legal-move?, that takes two arguments—from and to—which are the lists corresponding to source and destination pegs for a possible move. The predicate should return T if the top disk on from may legally be moved to to, and nil otherwise. Here are a couple of test cases, but you should create as many additional test cases as you need in order to be confident that your predicate is operating correctly:

   >(legal-move? ‘(1 3) ‘(2))
   T
   (a disk may be placed on top of a larger disk)

   >(legal-move? ‘(3) ‘(1 2))
   NIL
   (A disk may not be placed on top of a smaller disk)

4. Create a function move-A-to-B that takes a state as input. If the top disk from peg A cannot be moved legally to peg B the function should return nil; otherwise, it should return the state resulting from moving the top disk from peg A to peg B. Note that the function move-A-to-B takes a state as an argument, and returns either nil or a new state; i.e., it does not modify its argument.

            > (move-A-to-B '((1) (2 3) ()))
            (NIL (1 2 3) NIL)
            > (move-A-to-B '((1 3) (2) ()))
            (3 (1 2) NIL)
   

   > (move-A-to-B ‘(() (1) (2 3))) NIL
   > (move-A-to-B ‘((3) (1) (2))) NIL

   Again, create as many additional test cases as you need in order to be confident that your function sis operating correctly.

   Note: It is generally not good considered good practice to use Lisp primitives such as list, nth, etc., to directly create lists, or to access elements of lists. It is much better style to define your own problem- specific functions to create and access states, and to then use these within your functions. As an example, consider the functions make-state, farmer-side, etc., that we used in the farmer-wolf-goat-

cabbage problem in Week 3 labs. If you used primitives such as list or nth in your implementation of move-A-to-B, then you should rewrite this function to make use of problem-specific functions.

5. Define Lisp functions for the other required operators.
6. Define a parameter *operators* that stores the name of each operator. Initialise it appropriately.
7. Define a predicate solution-state? that takes a state as argument and returns T if that state is the solution state.
8. Perform breadth-first search using the Lisp search code that has been supplied.

Solving the Towers of Hanoi problem for different problem sizes:

Hopefully you have now used your program to solve the Towers of Hanoi problem with three pegs and three disks. Because the problem has a very small state space, the solution should be found very quickly. We would like to see how this performance varies as the number of disks is increased.

It should be straightforward to alter your code so that any number of disks can be used. Try running the program using 4 disks, 5 disks, etc., summarising your results in a table. The table should show how the statistics (i.e., number of nodes visited, maximum length of node list, length of solution, and maximum depth of search tree) depend on the number of disks.

Note: Rather than manually editing the code every time you change the problem size, it would be better practice to define a parameter *size* to store the problem size, and to initialise *start-state* and *goal- state* using this parameter.

Part B – Using a-star search

In Part A you wrote Lisp code for the Towers of Hanoi Problem, and used breadth-first search to solve the problem for different problem sizes. You probably found that the largest problem size that you could solve using breadth-first search (in a reasonable amount of time—such as a minute or so) was 7 (i.e., seven disks). For this question, you will use A-star search to solve the same problem.

In order to use the a-star search code which has been supplied in the file a-star.lisp, you will need to include the following two additional functions:

•   cost-of-applying-operator (state operator)

  This function should take a state and an operator as input parameters, and return the cost of applying the operator to that state. We will usually assume that all costs are equal, and hence this function should always return 1, irrespective of the state or the operator. Thus,

  (defun cost-of-applying-operator (state operator) 1)

•   estimated-distance-from-goal (state)

  This function takes a state as a parameter, and returns an estimate of the number of steps required to get from this state to the goal. Your task is to find a good heuristic and to code it in Lisp.

  Create a heuristic which will allow a-star search to solve the Towers of Hanoi problem on problem sizes larger than 7. Try to come up with most informed heuristic that you can think of. What is the largest problem size that it can solve in a reasonable amount of time (e.g., 60 seconds)? (Hint: the code for your heuristic will probably need to reference the global variable that stores the problem size; i.e., *size* , the number of disks).

Electronic files to be submitted

Submit the following three files using the CSE2AIF Assignment 1 submission tool on the LMS.

•   A file towers.lisp, that contains the LISP code for your program. The code should be saved with the problem size set to 3. Make sure that you include your name and student ID in the documentation at the top of the file.
•   A file demorun.txt, that contains a capture of a run of your program (see instruction for using dribble at the end of this document). The capture should commence before you load the code; i.e., we want to see the message displayed when your code is loaded into the interpreter.
•   A file towers.doc, that contains the table of results, and your comparison of the two algorithms in terms of spacae and time considerations on this problem. The table should show the performance of breadth-first-search and a-star for problem sizes from 3 up to the maximum size that the search algorithm can solve in a reasonable amount of time. For each case, record the number of nodes visited, the maximum length of node list, the length of solution, and the maximum depth of search tree. Make sure that you include your name and student ID in the document.

  Marking Criteria

  Your submission will be marked according to the following criteria:

  •   Functioning code that operates as specified above (16 marks) Your code will tested by evaluating the following function.

                 (defun test()
                    (load 'towers)
                    (load 'bfs)
                    (reset-stats)
                    (breadth-first-search *start-state* *operators*)
                    *stats*
    

    )

    Marks will be awarded for partial completion, or functions that contain some errors. If your code is incomplete, or has errors, you should provide annotated output to show what it can do.

  •   Programming style (6 marks)
    • –  Code displays good functional programming style (appropriate function and parameter naming,

      appropriate use of local variable definitions, state constructor and accessor functions, helper

      functions, etc.).

    • –  Appropriate and consistent documentation. Each function should contain documentation

      describing what the function takes as input, what is returned by the function, and side effects

      that the function has. Documentation should be concise, but clear.

    • –  Appropriate and consistent use of indentation. Indentation should be consistent in style, and

      should reflect the logical structure in the code.

  •   Heuristic (4 marks)
    Lisp code that implements a heuristic, which, when used in conjunction with a-star search, leads to significant improvement over breadth-first search. The documentation for the heuristic must include an English-language description of the heuristic.
  •   Table of results (4 marks)
    Your table of results comparing performance of breadth-first search with a-star search.

Directions for capturing a session using CLISP

The function dribble can be used to capture a session with the CLISP interpreter to a text file. To begin capture, call the function dribble with the double-quoted filename as an argument (if a file with that filename does not exist, it will be created, otherwise the session will be appended to the end of it). For example, the following command

      [1]> (dribble "sample.txt")

will cause the session to be captured to the file sample.txt. When you want to stop dribbling, call the function dribble without any arguments.

      [10]> (dribble)