QMCS 380 COURSE SYLLABUS

UNIVERSITY OF ST. THOMAS

DEPARTMENT OF QUANTITATIVE METHODS AND COMPUTER SCIENCE

 

COURSE NUMBER:

QMCS 380

COURSE NOTES:

Course notes accessible by students at http://courseweb.stthomas.edu/tpsturm/private/notes/qm380/index.htm

COURSE TITLE:

Artificial Intelligence and Robotics

ACADEMIC TERM:

Spring, 2006

CATALOG DESCRIPTION:

Theory and implementation techniques using computers to solve problems, play games, prove theorems, recognize patterns, create artwork and musical scores, translate languages, read handwriting, speak, and perform mechanical assembly.  Emphasis placed on implementation of these techniques in robots.

MINIMUM PREREQUISITES:

QMCS 220 - Statistics I and
QMCS 281 - Object-Oriented Design and Programming

IDEAL PREPREQUISITES:

Above prerequisites, plus all QMCS, Mathematics, and Philosophy courses numbered below 380 in the student’s planned program of studies

TIME AND DAYS:

Lecture:  1:35 to 2:40 P.M. on Mondays, Wednesdays, and Fridays
Lab:  2:55 to 5:55 P.M. on Mondays

MEETING ROOM:

415 OSS

INSTRUCTOR:

Dr. Thomas P. Sturm

OFFICE:

Room 424 OSS

TELEPHONE:

(651) 962-5479

E-MAIL ADDRESS:

tpsturm@stthomas.edu

 

WWW HOME PAGE:

http://courseweb.stthomas.edu/tpsturm/

 

OFFICE HOURS:

2:50 to 5:00 P.M. on Wednesdays and Fridays (some days only until 4:15).
You may also call for an appointment outside of these hours.

 

REQUIRED TEXTBOOKS:

(R) Rehg, James A.  Introduction to Robotics in CIM Systems.  Fifth Edition.  Prentice Hall.  2002.  ISBN 0130602434.
(A) Russell, Stuart and Norvig, Peter.  Artificial Intelligence: A Modern Approach.  Second Edition.  Prentice Hall.  2003.  ISBN 0137903952.

INSTRUCTOR-SUPPLIED TEXTBOOKS:

(H) Robotics and Industrial Electronics  (3 volumes)
(M) Robot Literacy:  A Laboratory Text in Applied Robotics
(B) Baum, Dave.  Definitive Guide to LEGO MINDSTORMS.  and  Extreme Mindstorms: An Advanced Guide to LEGO MINDSTORMS.
Laboratory manual and miscellaneous documentation

CREDIT STATEMENT:

This course satisfies an elective curriculum requirement for QMCS majors.  It does not fulfill the second level computer competency requirement, nor does it satisfy a requirement for the natural science, mathematical, and quantitative reasoning in the core curriculum.

DISABILITIES:

Students with disabilities who may need accommodations in any class are encouraged to contact the Enhancement Program – Disability Services at (651) 962-6315 as soon as possible.
Students with documented disabilities who may need classroom or exam accommodations must meet with me in my office before February 8.

COURSE PHILOSOPHY:

The purpose of this course is to make the student knowlegeable of the principles of various areas of artificial intelligence and able to apply those principles to the design of robotics systems.

COURSE OBJECTIVES:

1.  Provide the student with a firm grasp of philosophy of artificial intelligence and its methods.

 

2.  Provide the student with a firm grasp of the terminology and technology used in robotics systems.

 

3.  Overview the major results in searching, game playing, knowledge representation, reasoning, theorem proving, planning, learning, vision, and natural language processing.

 

4.  Obtain experience with multiple robotic systems.

 

5.  Understand robot classification, end-of-arm tooling, sensors, controllers, programming, designing robotic work cells, and applying those principles in a course project.

COURSE ASSIGNMENTS:

There are potentially six types of assignments for the course:  Robotics Labs, Written Assignments, Programming Assignments, Tour Reports, BlackBoard Assignments, and a Robotics Project.  Except for BlackBoard Assignments, all assignments must be submitted on 8˝ x 11 white paper, one side only, and stapled together.  In addition, an oral presentation of the Robotics Project proposal and final report must be given.  Written Assignments, Programming Assignments, BlackBoard Assignments, and Tour Reports are to be done individually by every student.  Robotics Labs and the Robotics Project must be done either individually or with at most one other lab partner, submitting a single report with both names.  Help in any form (including the internet) on any work must be properly acknowledged in writing.  Work is expected to be done in a professional manner.  All assignments are due at the beginning of class on the date due, or may be submitted at my office 30 minutes prior to class time.

WRITTEN ASSIGNMENTS:

Written assignments require that all work done in arriving at the solutions be shown.  Since written assignments will be discussed in class the day they are due, late written assignments will not be accepted, receiving a grade of 0.

PROGRAM-MING ASSIGNMENTS:

All programming exercises at a minimum must consist of a source code listing and printed output from sufficient runs to demonstrate that the program works correctly for the desired range of inputs.  Missing or erroneous assignment parts must be re-submitted, but will receive substantially reduced credit

TOUR REPORTS:

Should one or more tours be successfully scheduled, a written tour report is due one week after each class tour.  This report should contain three parts:
1.  A brief description of the tour, including date, time, place, what was seen;
2.  A summary of what was learned about robotics and its integration into manufacturing;
3.  A critique of how well robotics was being used, including what basic principles were being followed or violated.

BLACKBOARD ASSIGNMENTS:

Several assignments will require the use of the BlackBoard system.  Grading will be based on the quantity, quality, and timeliness of the work.

ROBOTICS LABS:

A formal laboratory report is required for some robotics labs.  Other labs require only the completion of a results form.  Details of the labs, contents of the lab reports, and a sample lab report are contained at the end of the syllabus.

ROBOTICS or AI PROJECT:

Each student must participate in a robotics or artificial intelligence project.  The project consists of two parts - a proposal due around midsemester (both written and oral), and a final report (both written and oral with demonstration) at the end of the semester.

EXAMS:

There are a total of three exams of equal weight, including the final exam.  Exam dates are fixed as shown on the Detailed Course Outline.  Students who will be unable to attend on the day of a scheduled exam (presumably for an imperative reason) must make special arrangements with the instructor prior to the exam date.  Late exams will be given, graded, and counted at the sole discretion of the instructor.  Unexcused absences from exams will incur the most substantial penalties.

COURSE AVERAGE COMPUTATION

Exams
Labs, Reports, Assignments
Project

50% of grade
35% of grade
15% of grade

GRADE GUIDELINES:

At the end of the semester, the point total in each category is divided by the points possible in that category, then that percentage is weighted as indicated above to calculate an overall percentage, which in turn is equated with a letter grade.  The ranges indicated below are intended as guidelines, not as absolutes.

 

92% to 100%

A

 

68% to 72%

C

 

88% to 92%

A-

 

64% to 68%

C-

 

84% to 88%

B+

 

60% to 64%

D+

 

80% to 84%

B

 

56% to 60%

D

 

76% to 80%

B-

 

52% to 56%

D-

 

72% to 76%

C+

 

below 52%

F

 

COURSE OUTLINE

Day No.

Date

Text Chapters

Topic(s)

1

1/30

R 1

Introduction to Robotics

2

2/1

A 1, 26

Introduction to Artificial Intelligence (Turing's Test) (Weak & Strong A.I.)

3

2/3

R 2

Robotics Classification Systems

4

2/6

H 1,2,3

Robotics Power Systems

5

2/8

M 1,4; A 25

Robot Kinematics

6

2/10

R 3

Automated Work Cells and CIM Systems

7

2/13

R 4

End-of-Arm Tooling

8

2/15

M 2,3

Robot Training and Sensor programming

9

2/17

H 7

Robot Data Acquisition

10

2/20

R 5

Automation Sensors

11

2/22

R 6

Work Cell Support Systems

12

2/24

R 7

Robot and System Integration

13

2/27

R 8

Work-Cell Programming

14

3/1

 

EXAM 1

15

3/3

M 5; B1,2

Robot Programming (Microbot and Lego Mindstorms)

16

3/6

R 9,10

Justification and Applications of Work Cells, Safety

17

3/8

H 8,9

Robot Data Handling and Speech Synthesis

18

3/10

M 6,7

Robot Programming (Microbot ArmBASIC)

19

3/13

H 10,11

Robot Interfacing and Applications (Hero-1)

20

3/15

M 8, R11

Acceptance and Future of Robotics

21

3/17

R12

Robotics Case Studies

22

3/27

A 2, 3

Intelligent Agents, Problem Solving by Searching (AI as Empirical Enquiry) (State Space Search)

23

3/29

A 4, 5

Informed Search and Exploration, Constraint Satisfaction (Control of State Space Search) (Genetic Algorithms) (Genetic Programming) (A* Search) (Heuristic Search)

24

3/31

A 6, 7

Adversarial Search, Logical Agents (Game Playing) (Minimax) (α-β Pruning) (Resolution)

25

4/3

A 8, 9

First-Order Logic & Inference(Predicate Calculus) (Automated Reasoning)

26

4/5

B 3

NQC

27

4/7

 

EXAM 2

28

4/10

B 3

NQC

29

4/12

A 10

Knowledge Representation (CYC Project) (Frames)

30

4/19

A 11

Planning (Strong Methods of Problem Solving) (Blocks World)

31

4/21

A 12, 13

Acting in the Real World, Uncertainty (Reasoning under Uncertainty)

32

4/24

B 17

Robot Communications

33

4/26

A 14

Probabalistic Reasoning

34

4/28

A 15, 16

Reasoning Over Time, Making Simple Decisions (Speech Recognition) (Expert Systems)

35

5/1

A 17, 18

Making Complex Decisions, Leaning from Observations (Machine Learning)

36

5/3

A 19,20

Knowledge in Learning, Statistical Learning Methods (Neural Networks) (Perceptrons) (Back-Propagation)

37

5/5

A 21, 22

Reinforcement Learning, Communication (Natural Language Understanding)

38

5/8

A 23, 24

Probabilitistic Language Processing, Perception (Vision)

39

5/10

A 27

(Philosophy) Will Robots Rule the World?

40

5/12

 

Project Reports

 

5/17

 

EXAM 3- 10:30 to 12:30 A.M.

 

LAB ROTATION OUTLINE

Lab Number

Date

Labs Due are Based Upon

Group 1

Group 2

Group 3

Group 4

Group 5

1

1/30

Lab Intro

Lab Intro

Lab Intro

Lab Intro

Lab Intro

2

2/6

M1, M2, B

M1, M2, B

H1,2&3, B

H1,2&3, B

H1,2&3, B

3

2/13

M3, B

H1,2&3, B

M1, M2, B

H4, B

H4, B

4

2/20

H1,2&3, B

M3, B

H4, B

M1&2, B

H13&14, B

5

2/27

H4, B

H4, B

M3, B

H13&14, B

M1&2, B

6

3/6

M5, M6, B

H13&14, B

H13&14, B

M3, B

H15&16, B

7

3/13

H13&14, B

M5, M6, B

H15, H16, B

H15, H16, B

M3, B

8

3/22

H15&16, B

H15&16, B

M5, M6, B

M5, M6, B

H17, M4, B

9

4/3

M7, B

H17, M4, B

H17, M4, B

H17, M4, B

M5, M6, B

10

4/10

H17, M4, B

M7, B

M7, B

B, Project

B, Project

11

4/24

B, Project

B, Project

B, Project

M7, B, Project

M7, B, Project

12

5/1

Project

Project

Project

Project

Project

13

5/8

Project

Project

Project

Project

Project

 

LAB DETAILS:

Lab Code

Details:  Lab Components are Based Upon

H1

Heathkit Experiment 1, Steps 1 to 29

H2

Heathkit Experiment 2, Steps 1 to 15

H3

Heathkit Experiment 3, Steps 1 to 5; Use of Digital Logic Probe

H4

Heathkit Experiment 4, Steps 1 to 25

H13

Heathkit Experiment 13, Steps 1 to 22

H14

Heathkit Experiment 14, Steps 1 to 14

H15

Heathkit Experiment 15, Steps 1 to 21

H16

Heathkit Experiment 16, Steps 1 to 29

H17

Heathkit Experiment 17, Steps 1 to 38

M1

Microbot Chapter 1, Activities 1 to 6

M2

Microbot Chapter 2, Activities 1 to 7

M3

Microbot Chapter 3, Activities 1 to 7 (using breadboard extension)

M4

Microbot Chapter 4, Activities 1 and 2 (no robot required)

M5

Microbot Chapter 5, Activities 1 to 7

M6

Microbot Chapter 6, Activities 1 to 6

M7

Microbot Chapter 7, Activities 1 to 10

B

Dave Baum’s books – Chapters 1 to 19, in sequence

Project

Work on course project after completing Baum’s books

Lab Reports for QMCS 380†

 

Background

 

Roboticists stand with a foot in each of two worlds.  On one side, they work in a technical world in which they use their understanding of natural laws, mathematics, computers, and engineering principles to design and analyze products and processes to ensure that they function as specified.  On the other side, they work in a commercial world in which they use their understanding of economics, psychology, and history to ensure that the specifications reflect the needs and desires of their customers.  Success in both worlds is dependent on the ability to communicate clearly.

 

Roboticists use project reports to inform their customers of the results of their work.  These customers might be co-workers in other departments, supervisors, engineers employed by suppliers or clients, or even successors unknown to the writer of the report.  The report must be clear enough to convey the purpose of the work, the method used, the results obtained, and recommendations resulting from the work.  In this class, your lab reports should demonstrate your written communication skills in addition to your understanding of the robotics techniques required for the successful completion of the lab exercise.

 

Format

 

You are free to format your report as you wish, but it must contain the following parts:

 

Title, Author, Date, Lab #  - In industry, your employer may also require that the report identify the project code, customer, or recipients of the report.  The purpose of this identifying material is to allow readers to quickly determine the subject of the report, who to contact with questions, and how to file the report.

 

Abstract - Any report that required more than a few seconds to read should have a single paragraph summary that allows potential readers to determine if the document is relevant to their own work.  This paragraph is alternatively called a synopsis or an executive summary.

 

Statement of Work - In industry and in this class, your work should be focussed on achieving objectives, otherwise you can expend a great deal of energy without obtaining useful results.  By including a statement of work or problem statement in your report, you are informing your reader what objectives your work achieves.  This helps the reader follow your reasoning as you describe your methods and results.

 

Method - In this section, you should describe your work in sufficient detail to allow a knowledgeable reader to verify your work.  Describe the hardware and software used in your tests, the test methods you used, and the limits of your equipment and methods.  The level of detail depends on the nature of your report.  In some cases, you may wish to report the serial numbers of instruments and robots used in your experiments so that instrument calibration can be verified.  In other cases a sketch of your experimental setup or reference to a standard operating procedure is sufficient.

 

Results - The results of your work should be presented with sufficient clarity that the reader can understand how they were obtained from your methods and how you used them to arrive at your recommendations.  There are many graphical and numeric ways to present data; choose the methods that provide the greatest clarity.  Always use your knowledge of measurement uncertainty and error propagation when presenting results.

 

Conclusions and Recommendations - A scientific paper ends with conclusions, a robotics report ends with recommendations.  Unless you are the final decision-maker in your company, your report should recommend a course of action.  The goal of science is to gain a greater understanding of the universe; the goal of robotics is to make our little corner of the universe a better place in which to live.  This can only happen through action.  Your report must recommend what that action should be.

 

 

Content

 

 The goal of the robotics lab report is clear communication.  This implies that the spelling and grammar of written portions should be correct.  Paragraphs should be structured so that each develops a single idea.  Keep your intended audience in mind and write your report so that it answers any questions that they might have.

 

Graphical portions of the report must also be clear.  Graphs should be clearly and logically labeled.  Axes must be labeled with both the name of the quantity displayed and the units of measure used.  If multiple quantities are displayed on the same graph, they must be clearly identified.  Diagrams showing equipment interconnections may be hand sketched but should be understandable to the reader.  Standardized symbols should be used whenever appropriate.

 

As with any other skill, learning to communicate clearly requires practice.  The lab reports in this course are iterative assignments.  If the initial report is unclear or inaccurate, you will have the opportunity to improve it until it is acceptable.  By the end of this course, you should be able to design robotics systems and document your design well.

 

†This material is borrowed heavily from ENGR 410 materials developed by Dr. Jeff Jalkio and Dr. Chris Greene

 

An example report, taken from a course in Digital Design, written by Dr. Jeff Jalkio follows.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 Bit Multiplier Design

 

Jeff Jalkio

ENGR 230

University of St. Thomas

 

22 November 2001

 

Lab #6

 

Abstract

 

We have designed a circuit for the Xilinx Spartan FPGA that multiplies two 4 bit unsigned binary numbers to produce an 8 bit result.  It is conficugered for manual operation on the digilent protoboard, but can be reconfigured to act as a multiplier module in a larger design.  The design uses only 14 configurable logic blocks and can operate at 50 MHz.

 

Statement of Work

 

Our goal is to produce a 4 bit multiplier circuit on the Digilent protoboard.  This circuit must accept two 4 bit unsigned binary numbers from the user and produce an 8 bit unsigned binary output.  A start signal from the user should trigger the operation.

 

Method

 

Interface: The multiplier (denoted as B) is entered via switches 5-8.  Switch 8 is the most significant bit (MSB) of the multiplier with a down position denoting a 1 and an up position denoting 0.  The multiplicand (A) is entered similarly via switches 1-4 with switch 4 being the MSB.  The product is displayed on the LEDs with LED 8 being the MSB and an illuminated LED denoting a 1.  Button 1 is pressed to provide the start signal.  The A and B inputs must be stable at the time start goes high.

 

Architecture: Our multiplier design has a simple add and shift architecture.  It is a synchronous design that uses the on-board clock generator to provide a single clocking signal for all flip flops.  It should be noted that no status output is described in the system requirements.  Our multiplier design provides a valid product 10 clock cycles after the rising edge of the start signal.  With the 25.175 MHz clock the LEDs should display a valid product approximately 25 microseconds after the start button is pressed, so an external done signal is superfluous.  However, we have included an internal done signal (as well as other internal signals) for testing purposes.  No debounce or synchronization circuits have been included for the A and B inputs, since they should be stable when start goes high.  Our control state machine has been designed so that the start signal need not be synchronized, as will be discussed in the theory of operation section.

 

The top level schematic in figure 1 describes our circuit.  We have created library modules for commonly used IO pins that are wired to switches and LEDs on the Digilent board.  Our design uses three standard parts from the Spartan library.  An 8 bit shift register (SR8RLE at E3) holds BX[7:0] (the shifted, zero extended multiplicand), an 8 bit register (FD8CE at G4) serves as our accumulator and a 2 bit counter (CB2CE at C6) provides a cycle count to our control logic.  We generated LogicBlox macros for the 8 bit adder at G6 and the 4 bit shift register for A[3:0] (the multiplier) at B3.  Finally, we implemented the state machine for the controller (MULTCNTL at E6) in ABEL as shown in the listing in figure 2.

 

Results

 

The circuit was simulated using two input test cases.  The first, 10*13 tests the case in which the LSB of A is 0 and the MSB is 1.  The second case 5* 14 tests the case in which the LSB of A is 1 and the MSB is 0.  Timing diagrams for these two cases are attached as figure 3.

 

After implementation, these two test cases were rerun, taking into account delays in the circuit.  A clock speed of 50 MHz was used to provide a factor of 2 safety margin in timing.  The circuit still functioned correctly.  The circuit uses 18 IO blocks, 24 of the 392 flip flops and 7% of the configurable logic blocks of the chip (14 CLBs).  The maximum combinational logic delay is 20.5 ns (through the adder) and the maximum net delay is 10.7 ns.  Since our clock period is approximately 40 ns, this leaves 9 nsec worst case for setup and clock to output delay in the flip flops.  For theXCS10PC84–3 part used, this leaves 6 ns of setup margin.

 

The resulting configuration bitstream was downloaded to the SPARTAN XCS10 on the Digilent board and tested by trained monkeys.  Unfortunately, the switches are too closely spaced for their fingers and they had trouble pressing the start button.

 

Conclusions and Recommendations

 

This circuit could be improved with a few very simple changes.  Numbers are usually written with the most significant bit on the left, so our assignment of switches and LEDs should be reversed to ease interpretation of the numbers.  Similarly, we could invert the sense of the input switches so that up denotes 1.  If I wanted to get an A in the course, I would do these things.

 

If this circuit were to be used for an ALU in a computer, we would need to provide the done signal as a control output.  Fortunately, this is easy to do.