βουλευόμεθα δ᾽ οὐ περὶ τῶν τελῶν ἀλλὰ περὶ τῶν πρὸς τὰ τέλη. οὔτε γὰρ ἰατρὸς βουλεύεται εἰ ὑγιάσει, οὔτε ῥήτωρ εἰ πείσει, οὔτε πολιτικὸς εἰ εὐνομίαν ποιήσει, οὐδὲ τῶν λοιπῶν οὐδεὶς (15) περὶ τοῦ τέλους· ἀλλὰ θέμενοι τὸ τέλος τὸ πῶς καὶ διὰ τίνων ἔσται σκοποῦσι· καὶ διὰ πλειόνων μὲν φαινομένου γίνεσθαι διὰ τίνος ῥᾷστα καὶ κάλλιστα ἐπισκοποῦσι, δι᾽ ἑνὸς δ᾽ ἐπιτελουμένου πῶς διὰ τούτου ἔσται κἀκεῖνο διὰ τίνος, ἕως ἂν ἔλθωσιν ἐπὶ τὸ πρῶτον αἴτιον, ὃ ἐν τῇ εὑρέσει ἔσχατόν (20) ἐστιν.
(We deliberate not about ends but about means. For a doctor does not deliberate whether he shall heal, nor an orator whether he shall persuade, nor a statesman whether he shall produce law and order, nor does any one else deliberate about his end. They assume the end and consider how and by what means it is to be attained; and if it seems to be produced by several means they consider by which it is most easily and best produced, while if it is achieved by one only they consider how it will be achieved by this and by what means this will be achieved, till they come to the first cause, which in the order of discovery is last. — Aristotle, Nicomachean Ethics Book III.3, 1112b, translated by W.D. Ross, 1908.)
Remember GPS? By now, “GPS” is a colorless term denoting a particularly stupid program to solve puzzles. But it originally meant “General Problem Solver”, which caused everybody a lot of needless excitement and distraction. It should have been called LFGNS-“Local Feature-Guided Network Searcher”. — D. McDermott, “Artificial Intelligence Meets Natural Stupidity”, SIGART Bulletin, 57, April, 1976, p. 4–9.

In this lab exercise, you’ll work with the General Problem Solver (GPS).

The General Problem Solver

The General Problem Solver (GPS) was an attempt by H. Simon, J. Shaw and A. Newell to build a universal problem-solving engine based on means-ends analysis (as articulated by Aristotle in Nicomachean Ethics, III.3). It was first developed in 1957 and written using the Information Processing Language (IPL - basically an assembly language with list processing). You’ll be using a Python implementation of the General Problem Solver (GPS) built by D. Connelly for P. Norvig’s Paradigms of Artificial Intelligence Programming text.

Exercise 1.1

To install the course Python tools and get started with the GPS implementation, do the following:

  1. If you haven’t already done so, create a Python virtual environment for this course, clone the course code repo, and fire up the IDE (see the guide). The course repo includes tool libraries for:

  2. Take a look at the gps.py file in the PAIP tools and answer the following questions:

    1. Is the GPS problem solver implemented as a class or as a function?
    2. The solver requires initial states, goal states and operators. Of what type are these objects?
    3. Is the mechanism recursive? If so, how does it implement its recursion?

  3. If you haven’t already done so, create your own course repo (again, see the guide), and create your own package for lab 1 (cs344/lab01).

  4. Copy monkeys.py into your new package, and get it to run. Then answer the following questions:

    1. What famous puzzle does this code model and what are the rules of that puzzle? Does the code faithfully implement the puzzle?
    2. How does the GPS mechanism solve the problem? Be prepared to specify this in detail. You can use the logging feature to print a trace of the mechanism’s deliberations.
    3. Is this code artificially intelligent? If so, which definition (or definitions) of AI from the text does it satisfy?
    4. Would a monkey who/that solves the problem in the real world be displaying intelligence?

Save the answers to these questions in a text file, lab_1.txt, so that you can submit them later.

The Blocks World

The blocks world is probably the most famous of the “toy” domains studied in AI. Familiarize yourself with the domain’s rules before proceeding.

Exercise 1.2

Load blocksworld.py and configure it to solve the following problems:

  1. blocks world example
  2. blocks world example

Save your program file for this exercise. Name it lab_2.py.

Limitations of GPS

In retrospect, GPS wasn’t very G; it’s P’s weren’t very interesting; and it didn’t always find an S. First, it turns out that planning for common problems in the blocks world is NP-hard, but this wasn’t well-understood in the early days of artificial intelligence. Second, there are limitations of the mechanism that had to be painstakingly identified and addressed over the years.

Exercise 1.3

Specify and implement a problem that GPS cannot solve. Special honor goes to those problems that you can solve but GPS can’t solve. When you’ve specified your problem, check to see if you can get things to work by manually re-ordering the sub-goals or operators.

Save a program file, lab_3.py, with your problem specification and comments.

In retrospect, one wonders what basis there was for the triumphalist quotes common in the early days of AI (e.g., these quotes from Herbert Simon in 1956 and 1958).

Checking in

Submit your solution by committing the files specified above to your GitHub repo under the directory cs344/lab01. We will grade your work according to the following criteria:

See the policies page for lab due-dates and times.