Outline The promise of autonomous explorers The challenge of autonomous explorers Agents great and small Course objective 1(16.410/13) Principles for Building Agents Course objective 2(16.413) Building an Agent The Mars exploration rover(MEr) project

Assignments · Remember: Problem set#1: Rules and Scheme due today September 15th, 2003 Reading Solving problems by searching: AIMA Ch 3 Homework for this lecture Problem set #2 due Monday, Sept. 22 Snas witha, Spring 03 Outline

Programming Languages · Control Conditionals Functions function calls Threads Data Scalars: booleans, numbers, strings Records/ structures Classes, types sept.8.2003

Constraint Satisfaction Problems: Formulation Brian C. Williams 16410-13 September 29th, 2003 Slides adapted fro 6. 034 Tomas lozano perez and AIMA Stuart Russell Peter Norvig Reading Assignments: Constraints Much of the material covered only in lecture slides

September 24, 2003 Scheme Tutor notes In scheme tutor stick to r5rs scheme The Tutor uses SCM, not miT scheme Strategy: click\Check\button on initial code, in order to view test cases pt.24,2003 16410/16413 Even more scheme

Out line Propositional Satisfiability Propositional Clauses Backtrack search Unit Propagation DPLL: Unit Propagation Backtrack Search Characteristics of dPLl local search using GSAT Propositional Clauses

Solving CsPs Solving CSPs involves some combination of 1. Constraint propagation eliminates values that cant be part of any solution 2. Search explores valid assignments Arc Consistency Arc consistency eliminates values of each variable domain that

Histol · Kautz and selman.1992 Inspired by improvements in satisfiabity algorithms Big Idea Encode planning problem as a(very large) logical formula Initial-state all-possible-actions goal Find a satisfying assignment to action-time propositions, and we have a plan

How do we maneuver ImagestakenfromNasa'Swebsitehttp://www.nasa.gov/ Roadmaps are an effective state space abstraction Brian Williams, Spring 0 Courtesy of U.S. Geological survey

Achieving Arc Consistency via Constraint Propagation Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc Directed arc (Vi, v) is arc consistent if VXED, 3yED, such that(x, y) is allowed by constraint C