TEACH POP11_PROJECT Aaron Sloman November 1999 CONTENTS - (Use g to access required sections) -- Introduction -- Objectives of the mini-project -- Techniques that your project will need -- Possible topics -- -- 1. A problem solver based on searching -- -- -- A route-finding program -- -- -- A puzzle solving program -- -- 2. A "natural language" front end -- -- -- A front end to LIB RIVER -- -- -- A conversational drinks machine -- -- -- A diary manager -- -- 3. A program to play a board game -- -- 4. An expert system (e.g. fault diagnosis, or planning) -- -- 5. An "object oriented" adventure game (possibly using SIM_AGENT) -- Other possible projects -- WARNING -- Formulating a proposal -- After the topic has been approved: a project plan -- Writing up the report -- Handing in the report -- What assessors will be looking for -- Introduction ------------------------------------------------------- The final exercise for the introductory Pop-11 programming course is to propose design, implement, and document a mini-project. The deadline for submission of the report will be announced separately. You will almost certainly find the project highly enjoyable but also very challenging. If you find the descriptions of possible mini-projects below too daunting at first, please note that some of the options have been designed to be much easier than others, and are supported by helpful TEACH files, whereas others are more challenging and require more independent work. The most important thing is not that you have to produce a very impressive or highly original project, but that that you should be able to do something that works, and then write a good report on it explaining what it is, how it works, and how it could be improved. You should also, in your critical discussion of your program, show evidence of having read about related work in AI. Of course, the difficulty of a project will be taken into account in awarding a mark. Tutors and demonstrators can help you cut down your project goals to a size that suits your abilities. Students who wish to collaborate on a project may discuss this with the tutor. They will have to hand in separate reports, each report making it very clear which portion of the work was done by whom and how the collaboration was managed. Below you will find a list of possible topics for your projects. If you think you have an alternative topic that you would prefer to work on please send a brief description as soon as possible by email to the person currently teaching your course. -- Objectives of the mini-project ------------------------------------- There are several important educational objectives o The project will help you consolidate your grasp of the language Pop-11 (many of whose features are also found in other programming languages). o You will have your first experience of designing a complete system yourself, starting from the process of specifying high level goals. This requires clarity of thought and an ability to think at different levels of abstraction, which will be very useful in many other contexts later on, both in your studies here and in your later career. o You will continue learning how to test your programs and to track down bugs. (Everyone produces bugs. More advanced programmers produce more advanced bugs. Learning techniques for tracking down problems, and fixing them, is very important for anyone who needs to be able to design working systems or explanatory models. Thus the bugs are an important part of the learning process.) o You will have experience of writing a report on your program. In fact it is mainly the reports that assessors will read, so you will need to be able to explain your objectives clearly, explain the design you developed in order to meet those objectives, demonstrate how far the program succeeds, and analyse its weaknesses and possibilities for future development. o If the project relates to published literature you will also learn how to report on things you have read and relate your own work to the work of others. In addition to these educational objectives the project will count as part of your assessment. That's less important! -- Techniques that your project will need ----------------------------- Your project should make use of a subset of the techniques that you have learnt this term. Depending on how much progress you have made since starting, these techniques could include: A. General programming techniques such as: - defining procedures that form a package that work together, passing arguments and receiving results - using a variety of syntactic control constructs including conditionals and loops of various kinds (while, for, foreach, etc.) - manipulating lists and other data-structures (e.g. words, strings, numbers) - describing programs (saying what they do and how they do it, at different levels of abstraction) B. Techniques that are more specifically relevant to designing intelligent (or "knowledge based") systems, including: - using lists and the pattern matcher to store and manipulate information about the chosen problem domain (E.g. TEACH RESPOND, RIVER2, MATCHES, DATABASE) - using a search strategy to permit the computer to find a solution to a problem by exploring combinations of alternatives (E.g. TEACH TOWER, SEARCHING) - using domain-specific heuristics to control the search - designing a simplified natural language interface to replace a typical programming command interface. (E.g. TEACH GRAMMAR, TEACH RIVERCHAT) - using rule-based programming (perhaps: See TEACH RULEBASE) - designing a simple expert system of some kind (E.g. TEACH SEARCHING, PRBWINE, RULEBASE, PRBRIVER) - for some students, learning to use object oriented techniques, based on classes, methods, and inheritance. (E.g. TEACH ADVENT_OBJECTCLASS, TEACH OOP) - for some students, learning to use the graphical facilities in POP11 (e.g. TEACH GSTART, RC_GRAPHIC) - for some students, learning to use the control-panel and menu facilities in POP-11 (E.g. TEACH RCLIB_DEMO.P, HELP RC_CONTROL_PANEL (and others) - for some students, learning to use the SIM_AGENT toolkit. (E.g. TEACH SIM_FEELINGS, TEACH SIM_AGENT) It isn't necessary for every student to address all these techniques. You may focus on a subset that relates to what you have learnt and your interests. -- Possible topics ---------------------------------------------------- Here is a list of possible project topics. Each of them is very open-ended. For students who are new to programming it would be possible to attempt a simple version of one of these. Those with more experience and fluency can attempt a more ambitious version. It is a fact of life that programming abilities vary ENORMOUSLY from individual to individual, so students who see others making much more rapid progress should try to do the best they can without letting the discrepancy cause depression or despair. You may need guidance on how to restrict your objectives to something that you can manage. Also remember that the primary assessment will not be on how much code you have written, but on how well you report on what you have and have not done, as explained below. Each of the following topics grows out of teach files, some of which you have already worked through, some not. -- -- 1. A problem solver based on searching Ideally every student should do a program that involves some searching, as this is such a basic and general aspect of AI (and intelligence). However for some students this may be too difficult, and one of the later options would then be more suitable. TEACH TOWER introduces basic programming techniques for searching for a solution to a problem. TEACH SEARCHING generalises this by showing you how to build a very general program that can be applied to a variety of problems for which a solution can only be found by searching in an abstract or concrete search space. Your project could complete the problem solver described in TEACH SEARCHING and show how to apply it to a few different problems, e.g. solving the river crossing problem, or some other. -- -- -- A route-finding program Another possible searching application, sketched in the teach file, is a program that finds routes. If you wish to work on this you could develop a program that explains how to get from any school in this university to any other school. You would need to study a map of the university to work out how to store information about portions of routes, and you would have to think about the form in which it would be useful for a person to be given information about how to get to another part of the university. It may actually be useful to go out and explore views from different parts of the university in order to be able to print out good advice. If you wish to create a map that can be displayed graphically, there are facilities in Pop-11 (e.g. TEACH GSTART, TEACH RC_GRAPHIC, TEACH FACES). TEACH * ROUTE introduces an existing library program that gives information about routes on the London underground network. It is also described in the appendix to Chapter 5 of the book by Sharples et al. If you decide to write a route-finding program you could use the format of that program for storing geographical information, or devise your own format. You need to think very clearly about the objectives of your program. Should it find all routes from A to B, or any route that works (no matter how devious), or the shortest route, or the route that satisfies some constraint specified by the user (e.g. "I want to go via the library".). -- -- -- A puzzle solving program There are many puzzles that require you to search for a solution by finding combinations of moves formed from basic actions, until you find a complex action sequence (e.g. a plan) that has the required properties. TEACH * TOWER gave a very simple example where the actions were all of the form "Select a block" or "Select a number". A different kind would be the river-crossing puzzle where the actions are of different sorts (put in X, get in, get out, take out X). You could select such a puzzle and design a program to solve it by searching. If possible it should be a puzzle that admits various initial states and different goal states, so that you can test the program with different combinations of initial and final states. E.g. a general program for solving the river puzzle would start with any legal combination of fox, chicken and grain on river banks and find a way to achieve any legal combination, e.g. everything on the right bank except the man and the chicken. Another kind of puzzle would be a sort of crossword puzzle. A program might be given a list of words, e.g. [cow eel elephant little love peel tone wine] And a puzzle in this form, where the dots represent spaces to be filled by letters from the words. The problem is to insert all the words consistently, with letters replacing the dots, and words going from right to left or top to bottom. [[# . . . . . . . . # . . . # #] [# . # # . # # # # # . # . # #] [# . . . . # # # # # . . . . #] [# # # # . . . . . . # # . # #]] In this problem the searching consists of trying different words in different locations. There are, of course, heuristics that could cut down the search. -- -- 2. A "natural language" front end -- -- -- A front end to LIB RIVER TEACH RIVER2 introduced you to commands like riv_putin("fox") => riv_getin() => riv_cross() => It might be much nicer (e.g. for a child) to be able to type in sentences in English such as Please put the fox in Put the fox in the boat Climb into the boat Join the fox in the boat Please row across Take the passenger out Put the fox on the bank Where is the chicken? Has anything been eaten? Will anything be eaten if I get in now? TEACH RIVERCHAT gives some ideas as to how you might do this. The simplest strategy would be to use the pattern matcher as in the TEACH RESPOND file to cater for all the different forms of utterance. TEACH TRAIN_CLERK introduces a possible project based on a simulated train clerk that answers questions about trains and sells tickets. More interesting would be to devise a grammar for the interaction language and use the parsing facilities in LIB GRAMMAR (described in TEACH GRAMMAR) to check whether a sentence is grammatical and if so produce a parse tree which can then be further analysed and interpreted. (This would be considerably more difficult than using simple pattern matching, but more general. Some possible techniques for this are illustrated in TEACH MSBLOCKS, but that may be too complicated for beginners.) If you did not finish TEACH RIVERCHAT, a relatively easy project would be to finish and extend that. A more ambitious project could apply the techniques to a different domain of conversation. -- -- -- A conversational drinks machine There are many variants of the previous idea. For example another one would be a "talking" drinks machine. You could type in questions about which drinks are available, how much they cost, whether they are hot or cold, etc. The machine should also be able to tell you what change you would get if you put in a pound coin, or a five pound note, and so on. It should be able to tell you if it is out of some ingredient, and perhaps suggest an alternative: Sorry I am out of milk, so would you prefer black coffee or hot chocolate? You could do this using the database to store information about the state of the machine, and a matcher-based conversational controller, as in TEACH RESPOND and TEACH RIVERCHAT. (See also TEACH DATABASE, RIVER2) Could you extend the drinks machine so that it gives you advice on which sort of drink would suit you, depending on how how the weather is, whether you are soon going to bed, how much money you have, what kinds of drinks you like, whether you like milk or sugar, whether cafeine keeps you awake, whether you are on a diet, etc. Perhaps, when the machine is out of change, if you tell it which coins you have, it could tell you which combination of the coins adds up to the total required for the drink you have chosen? If you have learnt to use some of Pop-11's graphical facilities as described in TEACH FACES and TEACH RC_GRAPHIC you could add a graphical display of the contents of the drinks machine, showing how it changes. -- -- -- A diary manager One example would be to write a diary manager program which keeps track of all your appointments using the Pop-11 database, and has conversations with you in English, accepting information about new appointments, asking questions about appointments already in the database. A nice extension would be to have the diary manager give you advice as to the best way to schedule some of your meetings. E.g. if you have to meet X in Birmingham, Y Coventry and Z in London, what would be good days to have the meetings? Or if you have to see A for two hours, B for one hour C for an hour and a half, which would be the best way to fit these into slots in your existing diary. Can you see some link with TEACH * TOWER here? -- -- 3. A program to play a board game There are many "board" games of varying degrees of complexity, including noughts and crosses (tic-tac-toe), a generalisation called GO-moku (where four in a row wins on a 19 by 19 board), another generalisation called Connect four (where you drop coloured disks down vertical channels, nim, othello, mastermind, chess, drafts (checkers), fox and hounds, and many more. Writing a complete program to play a game from beginning to end can be quite difficult, even for a simple game by noughts and crosses. A possible project is to select a game and then develop one or more parts of a game playing program. E.g. the first part might manage a representation of the board, read in moves, check whether moves are legal, check whether one side or the other has won, and display the board along with any relevant messages. That could be combined with a "random" move generator to play the game. Alternatively, having got that far you could try to develop programs to choose a good move. That might involve procedures which detect threats that need to be blocked and opportunities for good moves, and perhaps some way of ordering possible moves. In general a good player may have to search through alternative combinations of moves of both players to find out what the consequences of various moves are, before deciding which move to adopt. (Compare searching through possible moves in order to decide how to get the fox chicken and grain across the river.) For a first mini-project a complete game playing program is probably too ambitious, so aim for a partial one, and then if you have time, you can complete it. -- -- 4. An expert system (e.g. fault diagnosis, or planning) TEACH * RULEBASE introduces the use of a forward chaining production system to design a very simple expert system. More complete information is available in TEACH * POPRULEBASE, and even more(!) can be found in HELP * POPRULEBASE. Several demonstration programs are provided, which you might wish to extend. TEACH * PRBWINE introduces an expert wine adviser. You could turn it into something more general. This sort of thing is fairly easy, as there is not really any problem-solving involved, just chatting to narrow down options. Perhaps it is too easy? TEACH * PRBZOO gives a rule-based program for identifying animals from their descriptions. This can be very simple, perhaps too simple. However, it could be extended in some way, e.g. so that the program learns. TEACH * PRBGROCERIES This is about a program for packing groceries into bags at a supermarket checkout point. You could try extending to to cope with more types of items and more constraints (e.g. don't put uncooked meat or fish in the same bag as cooked meat or fruit). TEACH * PRBRIVER shows a much more complicated example, where the computer works out a plan for solving the river-crossing problem. You could try to design either a fault-diagnosis system or some kind of planning system (more difficult). For example if you have a car or some kind of machine that has a manual with a section concerned with "trouble-shooting" you could find a way to give the computer the information that is in the manual. Another possibility would be to look at Benjamin Spock's book on Baby and Child Care, or some other home medicine book, and design a little expert system to help parents decide whether a baby should be taken to the doctor or not, on the basis of different combinations of commonly occurring symptoms. TEACH * EXPERTS gives an overview of some types of expert systems and relevant facilities in Pop-11. The standard text books on AI give further information that could give you ideas. -- -- 5. An "object oriented" adventure game (possibly using SIM_AGENT) This one is potentially quite difficult as it involves a lot of new concepts. It is probably most suitable for students who have had prior programming experience before starting this course. If you have found all the programming so far very easy, and you have worked through TEACH SEARCHING and TEACH GRAMMAR, you could try to teach yourself about "Object Oriented Programming" using the introduction provided in TEACH OBJECTCLASS_EXAMPLE. (This explains and illustrates notions of classes, methods, and inheritance.) See also TEACH OOP Then having done that you could work through TEACH ADVENT_OBJECTCLASS to get some ideas on how to design a simple adventure game. On that basis you could try extending the adventure game, either by making the players more intelligent, or by adding a natural language interface of some kind, e.g. using the ideas in TEACH RIVERCHAT. More detailed suggestions are included in TEACH ADVENT_OBJECTCLASS Another possibility would be to use the Objectclass facilities as a basis for the conversational drinks machine described above, instead of using the database for the simulation. The file TEACH SIM_FEELINGS introduces the SIM_AGENT toolkit which provides a framework for designing simulation in which a collection of agents interact with one another. This could be the basis of a quite ambitious project. -- Other possible projects -------------------------------------------- There are MANY other possibilities for projects, including simple teaching programs, simple learning programs, simple picture analysing programs, and many more. If you wish to do something different from all the above, and you have an idea that you feel confident you could work on, you could make a proposal. Every project topic must have been approved in advance by the course tutor. The project should include the use of lists to store knowledge about something, and the use of the pattern matcher or database procedures to access information in lists. Ideally it should involve some searching to find a solution to a problem. For additional example project topics look at TEACH * PROJECTS -- WARNING ------------------------------------------------------------ Each of the above topics is potentially something on which you could spend far more time than you will have available. So it is important that you do NOT aim to design an all-singing all-dancing program that does everything that could possibly be required for the task you have chosen. It will be enough if you design, implement, test, and report on an ILLUSTRATIVE SUBSET of the facilities. Your report can mention the ways in which the program is incomplete and might be extended. Some students who enjoy programming will find this warning very hard to remember and will therefore spend far too much time on the programming, and as a result may not have enough time to produce a good report. Remember the report is the most important thing you have to hand in: the program is merely background. -- Formulating a proposal --------------------------------------------- Before you finally decide on your project it is important that you write a first draft proposal for approval by your tutor, and then a more detailed proposal after your topic has been approved. The first draft proposal should: a. Describe the domain b. Give some examples of the kind of behaviour you would expect your program to produce (a mini-scenario). c. Sketch the strategy you intend to follow implementing the program (Referring to relevant teach files if appropriate) This proposal should be NO MORE than one page one. -- After the topic has been approved: a project plan ------------------ Having had the topic approved, you should try to expand your proposal into a project plan, which should have all the following sections: a. A brief description of the problem domain (e.g. see the list of possible topics, above.) b. A first general statement of the problem you intend to solve in that domain, i.e. a summary of what the program will actually do, and what it is for. c. Some brief examples of the kind of behaviour you would expect your program to produce (some scenarios). d. An outline "ontology" for the program, i.e. the kinds of objects properties, relationships, events and processes that you expect your program to know about. (Some kind of tree-structured diagram showing the different classes of objects and their properties could be useful here.) (NB this ontology concerns the things in the world not the things in the program. E.g. rivers, boats and animals, not lists, words, numbers, objectclass structures.) e. Plans for the form in which the information about these things will be stored in the program. E.g. will you use the Pop-11 database, or perhaps something else (e.g. Objectclass structures)? f. A list of the main procedures and how they will work. (Diagrams may help here.) g. A timetable for doing the various bits of the task, including writing the report. This project plan could be between three and five pages in length. It will provide an important checklist for you as you work on the project. You are likely to change your plan as you learn more about the problems through designing and testing the programs. As that happens you can modify the plan, but there should always be a *current* plan representing what you are doing and how and when. TEACH * PROPOSALS may give you some ideas on how to plan your project. -- Writing up the report ---------------------------------------------- TEACH * REPORTS makes a number of suggestions regarding how to write up a report. You are not obliged to stick to the format proposed there, but if you deviate from it then you should have good reasons. NOTE: You should find out the length requirement for your report, and make sure that the main report does not exceed that length. You can added extra material in the program listings and other appendices. (See HELP WC for a Word Counting program). You can use HELP RNO and HELP VED_RNO to find out how to format the text, number pages automatically, etc., if you write your report using VED. More ambitious students may wish to learn to use Latex. See TEACH LATEX, TEACH LATEX.TEX The report must NOT be handwritten. -- Handing in the report ---------------------------------------------- You will be given a special "cover sheet" that you should use as the front page of your report. This should show the TITLE of your project AS WELL as the course title. (Every project should have a descriptive title: not just "programming project".) Make sure that your report is submitted in a form that is convenient to read. Do NOT hand in fan-folded pages direct from the printer: separate the pages, trim them (i.e. remove sprocket holes), and staple or clip them together with the cover sheet on top. Aim to get it all printed out at least three days before the deadline: one of the unfortunate laws of nature is that computers or printers always break down just before deadlines, so if you leave things till the last moment there will be no excuse for late submission. -- What assessors will be looking for --------------------------------- Marking examinations, essays and project reports, like so many other things is a very subjective process. However you may find it helpful to be aware of some of the considerations that markers take into account when assessing projects. There is a list of possible factors described in TEACH * AI1PROJECT.CHECKLIST Which of these factors are actually used will depend on the stage the student is at and the type of project. In general first year projects will be examined more leniently than more advanced projects. Important points to watch out for are these (see TEACH REPORTS): 1. Your report must explain how ANY person can run your program without being logged in as you. Give instructions on how to test your program, including explicit examples of what to type in. This should be in an appendix, clearly identified in the table of contents. That means that any files or directories must be named by the full explicit path name. Also any files that load other files must load them via the full path name (unless they are all in the same directory in which case one can load the files from that directory). This also means that any directory your files are in must be readable by anyone, as must the files themselves. 2. Your report should explain very clearly WHAT the program does, HOW it does it, what works and what doesn't, and what its strengths and weaknesses are. 3. Your report should not mix up levels of explanation, and in particular should not go into great details in the form of a line by line explanation of the programs. Separate the description (WHAT) from the explanation (HOW). 4. Your report should include some examples of the program working, but should NOT include lengthy indigestible sections of program printout, such as can be produced by TRACE. 5. Your report should clearly acknowledge any use of programs produced by other people, including programs copied from TEACH FILES. 6. Grammar, spelling and English style should be good. Make sure that you proof-read the report before handing it in. Last-minute corrections can be made in ink if necessary. It is desirable to get another student to read a draft of your report and make comments on its clarity, interest, etc. You should do the same for other students. 7. The report should show that you have learnt more about AI than you could have got simply by doing Pop-11 exercises and attending lectures. Your reading of AI textbooks, journals, conference proceedings, etc. will help. REMEMBER: the educational value to you of doing the project and producing the report on it are of far more importance than its role in assessment. --- $poplocal/local/teach/pop11_project --- The University of Birmingham 1999. --------------------------------