Agents (Subsystem of AIMA Code)

The agents subsystem covers the code in Part I of the book: the basic environment simulator run-environment; simulations for the vacuum and wumpus worlds, and some simple agents for those worlds. It also includes the abstract class grid-environment, which is an environment that supports physical objects located in a two-dimensional rectangular grid of spaces. It serves as the basis for the vacuum and wumpus worlds, as well as for more complex environments like the shopping world of Chapter 8.

agents/: agents/environments/: agents/agents/: agents/algorithms/:

File agents/test-agents.lisp

File agents/environments/basic-env.lisp

The basic environment simulator code

This file defines the environment simulator function: RUN-ENVIRONMENT. It is a little different from the pseudo-code in the book: to make it easier to write new environments, we used an object-oriented approach. Rather than requiring the caller to pass in a bunch of functions to RUN-ENVIRONMENT, you will define methods for the functions for each subtype of environment. We added a DISPLAY parameter to control whether intermediate results are displayed. As an example, the following expression builds an environment and runs an agent in it, displaying the results:

(run-environment (make-vacuum-world :aspec '(random-vacuum-agent)))

We also define AGENT-TRIALS to compare the performance of several different agents in a series of random environments, all drawn from an environment subtype. For example to run 2 agents in 20 environments each:

(agent-trials 'vacuum-world '(random-vacuum-agent reactive-vacuum-agent) :n 20)

environment type (agents step max-steps stream initialized state)

The world in which agents exist.
An agent is something that perceives and acts. As such, each agent has a slot to hold its current percept, and its current action. The action will be handed back to the environment simulator to perform (if legal). Each agent also has a slot for the agent program, and one for its score as determined by the performance measure.

agent type (program body score percept action name)

Agents take actions (based on percepts and the agent program) and receive a score (based on the performance measure). An agent has a body which can take action, and a program to choose the actions, based on percepts.

Top level functions

run-environment function (env)

Basic environment simulator. It gives each agent its percept, gets an action from each agent, and updates the environment. It also keeps score for each agent, and optionally displays intermediate results. [p 48]

agent-trials function (environment-fn agent-types &key n)

Report how well a single agent does in a set of N similar environments, and compare that to other agents in the same set of environments. Environment-fn takes a :agents keyword argument, and returns an environment. Agent-types is a list of names of functions that each create an agent.

Generic Functions that must be defined for each environment

For each new type of environment you want to define, you will need a defstructure that inherits from (includes) ENVIRONMENT, and you will need to write new methods (or inherit existing methods) for each of the following eight functions. Here are the ones that will change for each new environment:

get-percept method ((env environment) agent)

Return the percept for this agent.

update-fn method ((env environment))

Modify the environment, based on agents actions, etc.

legal-actions method ((env environment))

A list of the action operators that an agent can do.

performance-measure method ((env environment) agent)

Return a number saying how well this agent is doing.
Here are the ones that can usually be inherited:

initialize method ((env environment))

Called once to do whatever is necessary to set up the environment for running the simulation.

termination? method ((env environment))

Return true if the simulation should end now.

display-environment method ((env environment))

Display the current state of the environment.

display-environment-snapshot method ((env environment))

Display a 'picture' of the current state of the environment.

Auxiliary Functions

run-eval-environment function (env)

Basic environment simulator; the same as run-environment. [p 48] We decided it was silly to run the environment and NOT eval the agents, so in this code, and in future editions of the book, we will only have RUN-ENVIRONMENT, and it will evaluate the agents.

agent-trial function (environment-fn agent-type env-gen-random-state n)

Run n environments with an identical agent in each, and average the scores.

execute-agent-actions function (env)

Each agent (if the agent is alive and has specified a legal action) takes the action.

print-structure method ((env environment) stream)

File agents/environments/grid-env.lisp

Environments with a two-dimensional grid layout occupied by objects

This file defines a GRID-ENVIRONMENT, a kind of environment where there is a rectangular grid of spaces, each potentially containing objects. (Notice that the ENVIRONMENT makes no mention of space or objects.) You won't be creating instances of grid-environment directly, but it is the key structure that is inherited by the Vacuum, Wumpus, Shopping and Elevator worlds.

grid-environment type (size grid objects start aspec bspec cspec)

object type (name alive? loc bump size color shape sound contents max-contents container heading)

An object is anything that occupies space. Some objects are 'alive'.

obstacle type nil

wall type nil

agent-body type (holding)

An agent body is an object; some bodies have a hand that can hold 1 thing.

Generic Functions

update-fn method ((env grid-environment))

Execute the actions and do bookkeeping on the bump sensor.

legal-actions method ((env grid-environment))

initialize method ((env grid-environment))

Build a new environment with all the agents and objects in place. This gets passed an environment which may need to have the objects placed. See PARSE-SPECS below in this file for more on initialization.

termination? method ((env grid-environment))

By default, we stop when there are no live agents.

display-environment-snapshot method ((env grid-environment))

Show what is in each location in the environment.

print-structure method ((object object) stream)

Show an object's name, and if it is alive, the direction it faces.

Actions

speak method ((env grid-environment) agent-body sound)

The agent emits a sound.

turn method ((env grid-environment) agent-body direction)

The agent changes its heading by turning right or left.

forward method ((env grid-environment) agent-body)

Move the object to the location that is one step directly ahead of it.

grab method ((env grid-environment) agent-body &optional args)

Grab an object at the specified location. Assumes a one-handed agent.

grabable? function (object)

release method ((env grid-environment) agent-body &optional args)

Release an object that is in the hand, putting it at the specified loc.

Initializing Environments

The grammar for the object-specs language is as follows: 

   specs  =>  (spec...)
   spec   =>  (AT where what...) | (* n spec...) | what
   where  =>  EDGE | ALL | FREE? | START | (x y) | (AND where...)
   what   =>  object | type | (type arg...) | (* n what...)  | (P x what...)
   n      =>  integer | (+- integer integer)
 
 The location FREE? means a randomly chosen free loc, ALL means every loc.
 If no location is specified, the default is START for agents, FREE?
 otherwise.  
 
 Examples of spec:
 
  (at edge wall)                  1 wall in every perimeter location
  (at free? wumpus)               1 wumpus in some random free location
  wumpus                          Same as above 
  ask-user-agent                  1 ask-user-agent in the start cell
  (* 2 apple)                     An apple in each of 2 random locations
  (* 2 (apple :color green))      A green apple in each of 2 random locs
  (at all (p 0.25 dirt))          All free locations have 1/4 chance of dirt
  (at (2 3) (* 8 apple) sign)     Location (2 3) has 8 apples and a sign
  (* (+- 10 4) apple)             10 plus or minus 4 (at random) apples
  (at (and (1 2) (1 4)) cashier)  These two locations each get a cashier
  (* 2 smoke fire)                2 random locs get both smoke and fire

parse-specs function (env specs)

Place objects, defined by specs, in the environment.

parse-spec function (env spec)

parse-where function (env where whats)

parse-whats function (env loc what-list)

parse-what function (env loc what)

Place the objects specified by WHAT-LIST at the given location The default location is START for an agent, random otherwise. The notation (P 0.5 what...) means 50% chance of placing each what, and (* n what...) means place n copies of each what.

parse-n function (n)

make function (type &rest args)

Make an instance of the specified type by calling make-TYPE.

random-loc function (env &key if tries)

Return a random loc, somewhere in the environment. The loc must satisfy the :IF predicate. If it can't find such a location after a number of TRIES, it signals an error.

free-loc? function (loc env)

A location is free if there is no obstacle there and it is not the start.

File agents/environments/vacuum.lisp

The Vacuum World: cleaning up dirt in a grid

dirt type nil

vacuum-world type nil

A grid with some dirt in it, and by default a reactive vacuum agent.

Defining the generic functions

performance-measure method ((env vacuum-world) agent)

100 points for each piece of dirt vacuumed up, -1 point for each step taken, and -1000 points if the agent does not return home.

get-percept method ((env vacuum-world) agent)

Percept is a three-element sequence: bump, dirt and home.

legal-actions method ((env vacuum-world))

Actions (other than the basic grid actions of forward and turn)

suck method ((env vacuum-world) agent-body)

shut-off method ((env environment) agent-body)

File agents/environments/wumpus.lisp

The Wumpus World Environment

wumpus-world type nil

A dangerous world with pits and wumpuses, and some gold.

wumpus-agent-body type nil

The default wumpus agent body is given an arrow.

gold type nil

pit type nil

arrow type nil

wumpus type nil

Defining the generic functions

update-fn method ((env wumpus-world))

termination? method ((env wumpus-world))

End when some agent climbs out, or for the default reason (everyone dead).

performance-measure method ((env wumpus-world) agent)

Score 1000 for getting the gold, with penalty of 10000 if dead and penalty of 1 for each step taken.

get-percept method ((env wumpus-world) agent)

Perceive stench, breeze, glitter, bump, and sound.

legal-actions method ((env wumpus-world))

In the wumpus world, agents can move around, grab gold and shoot arrows.

deadly? function (object)

Pits and live wumpuses are deadly.

Actions

climb method ((env wumpus-world) agent-body)

Climb out of the cave.

shoot method ((env wumpus-world) agent-body)

propagate-arrow function (loc heading env)

An arrow keeps going until it kills something or hits a wall.

kill function (object)

Make the object no longer alive.

File agents/agents/agent.lisp

Definition of basic AGENT functions

ask-user-agent type nil

An agent that asks the user to type in an action.

ask-user function (percept)

Ask the user what action to take.

print-structure method ((agent agent) stream)

Agents are printed by showing their name (or body) and score.

initialize-agent-names function (env)

Name the agents 1, 2, ... if they don't yet have a name.

File agents/agents/vacuum.lisp

Some simple agents for the vacuum world

random-vacuum-agent type nil

A very stupid agent: ignore percept and choose a random action.

reactive-vacuum-agent type nil

When you bump, turn randomly; otherwise mostly go forward, but occasionally turn. Always suck when there is dirt.

File agents/agents/wumpus.lisp

Agents for the wumpus world

wumpus-agent type nil

The default wumpus agent gets an arrow.

random-wumpus-agent type nil

aimless-wumpus-agent type nil

This agent does the obvious reactive things: grab when there's a glitter, and turn and move when there's a bump. If the wumpus is alive and there's a stench, it turns and moves. Otherwise it wanders aimlessly.

File agents/algorithms/grid.lisp

Algorithms for manipulating objects in a grid

grid-contents function (env loc)

Return a list of objects in this location, optionally including objects that are contained within containers here.

move-object-to function (object loc env)

Move an object to an absolute location and return that location. However, attempting to move into a location with an obstacle fails (returns nil) and the object receives a bump.

place-object function (object loc env &optional initial?)

Put the object in its initial position or a new position in environment.

place-in-container function (object container env)

Put the object inside the container, if there is room.

remove-object function (object env)

Remove the object from its current location.

find-object-if function (predicate loc env)

Return an object in this location that satisfies this predicate.

find-neighbor-if function (predicate loc env)

Return an object in a neighboring square that satisfies the predicate.

find-object-or-neighbor-if function (predicate loc env)

Return an object either in loc or a neighboring square that satisfies the predicate.

near? function (loc1 loc2 &optional tolerance)

Are the two locations nearby each other?

Maintaining and manipulating orientation

add-locs function (&rest locations)

Coordinate-wise addition of locations: (add-locs '(1 2) '(10 20)) = (11 22)

subtract-locs function (&rest locations)

Coordinate-wise subtraction of locations.

heading->string function (heading)

Convert a heading like (0 1) to a depictive string like ^.

absolute-loc function (agent-body offset)

Return an absolute location given an offset from an agent, taking the agent's orientation into account. An offset of (1 2) means 1 square to the right and two ahead of the agent, given its present orientation.

offset-loc function (agent-body loc)

Return an offset from an agent that corresponds to the absolute loc.
AIMA Home Authors Lisp Code AI Programming Instructors Pages