Introduction to AI - Week 10

Reactiveness

• Classical AI: Build systems based on carefully selected knowledge representation to model parts of the world

• Antithesis to classical AI: Obtain complex, apparently goal directed and intentional behaviour in a system which has no long term internal state and no internal communication.
  "Intelligence without Reason" [Rodney Brooks, 1991]

Key Concepts

• Situatedness: The world is its own best model
• Embodiment: The world grounds regress
• Intelligence: Intelligence is determined by the dynamics of interaction with the world
• Emergence: Intelligence is in the eye of the observer

Inspired by biological systems:

• Study complete integrated intelligent autonomous agents.
• Agents embodied as mobile robots in unmodified worlds.
• Agents should be situated, e.g. operate equally well when visitors walk through their workspace.
• Timescales are commensurate with those used by humans.

Principles of Computation

• Computation is organised as an asynchronous network of active computational elements (augmented finite state machines).
• Messages sent over connections have no implicit semantics - they are small numbers (typically 8 or 16 bits). Meaning dependent on the dynamics designed into both the sender and receiver.
• Sensors and actuators are connected to this network, usually through asynchronous two-sided buffers.

Consequences

• The system is reactive, but not purely reactive (may have state).
• Any search space must be quite bounded in size.
• There is no separation of data and computation (both distributed over the same network).
• There is no central model of the world.
• There is no central locus of control.
• There is no separation into perceptual, central, and actuation systems.
• Behavioural competence improves by adding more specific network to the existing one.
• There is no hierarchical arrangement.
• The layers, or behaviours, all run in parallel (conflict resolution may be necessary).
• The world is often a good communication medium for processes within a single robot.

Reactivity - Example

• Task: wander around looking for soda cans and bring them to the starting point.
• Sensor:
  • laser scanner for detecting objects,
  • infrared proximity sensors to navigate by following walls and going through doorways,
  • magnetic compass to maintain a global sense of orientation,
  • sensors in the arm to reliably pick up cans.
• Program:
  • no state longer than three seconds.
  • no internal communication between behaviour generating modules.

Example (Cont'd)

• Actuators driven by an arbitration network (fixed arbitration).
• World as model and communication medium:
  • Laser-based soda can object finder drove the robot so that its arm was lined up in front of the soda can, but didn't tell the arm controller to pick.
  • The arm monitors the motion. No body motion ==> motion of the arm so that soda can between fingers. Independently, grasp reflex that operated whenever something broke an infrared beam between the fingers.
  • By this kind of encoding it is possible that a human hands a soda can to the robot.

Discussion

• Try to model onto-genesis (individual development) by phylo-genesis (development of the species), i.e. the development of intelligence rather than the end product.
• It is possible to model low level animals like ants that way.

Open problems:

• Emergence: How to predict global behaviour of set of robots?
• Synthesis: Given a task, how to automatically derive a program for a set of robots?
• Communication: Which amount of communication?
• Cooperation & Interference: How to coordinate?
• Density dependence: How many robots?
• Individuality: Different individuals?
• Learning: What & how to learn?

Compromise: Reaction-First Search

Assume situated agent: system consists of a planner and a reactor.

• Principle of independent competence, i.e., reactor is able to take action with and without a plan:
  • When the reactor is told to act, it executes the currently available plan and then falls back on a reactive program.
  • If complete plan: reactor executes plan.
  • If no plan: reactor follows a programmer-provided reactive program (e.g. minimise Manhattan distance).
  • If a prefix plan available: the plan takes the reactor part of the way, the reactive program takes over at the plan's end.

The Problem

• If the reactor executes a prefix plan before that plan is known to lead to a solution, how can we be sure that this will not impair the reactor's performance?
  (Note: Search is an essential part of problem solving since there is no purely "local" way to guarantee that any given prefix plan can be extended to a solution.)
• Solved by rfs , monotonically increase goal satisfaction probability of the reactor, no matter how much time is spent searching. Planner releases prefix plans computed in the time available.
• A trajectory is a sequence of operator applications, each trajectory models one possible behaviour of the reactor.
• A prefix plan for a problem is a trajectory in which the first actions are specified by a prefix.

The Principles of Reaction First Search

• All states in the policy-defined subtree must be expanded before all other states in the search space.
• After selecting a level in the search tree by any means, a policy state in that level must be randomly chosen for expansion.
• In any given policy state, policy-recommended operators must be randomly chosen for application.

Then: Performance of rfs is monotonically increasing.

Example Scenario

Task: phase A - start at I go to G, grasp something, and phase B - go back to I.

Policy: in phase A and B reduce Manhattan distance between current position and G and I respectively.

Note: non-deterministic behaviour, in particular the reactor might be trapped.

The Planner in the Example

• Calculate probability that the policy will lead the agent into a dead-end. The procedure accepts an initial and goal location and return the probability that the agent will become trapped in a dead-end via the execution of the policy. Minimise probability to be trapped by prefix plan.

Summary

• Biological systems suggest that reactivity and deliberation play a significant role. In particular in humans both aspects are important (the first for short term goals and fast reaction, the latter for long term goals and slow reaction). Hence a more complicated architecture is necessary.

Intelligent Agents

• A system that perceives and acts [Russell-Norvig].
• A proactive system with its own goals and intentions.

Depending on the level of sophistication an agent should have, we need different architectures. We will look at the architecture of a learning agent, a more sophisticated single-agent architecture, and a multi-agent scenario.

Learning Agent

Learning agent has learning element and performance element

• The learning element is responsible for making improvements. It takes knowledge about the performance element & some feedback, determines how to modify performance element.

• The performance element takes in percepts and decides on external actions.

• The critic tells learning element how well the agent is doing (and has itself a fixed standard of performance).

• The problem generator suggests actions that will lead to new & informative experience.

Russell/Norvig's Learning Agent

A General Agent Architecture by A. Sloman

Characteristics of Intelligent Agents

• "Autonomy: Agents should be able to do most of their tasks without any direct assistance from an outside source."
• "Social Ability: Agents should be able to interact with, when they deem appropriate, other software agents and humans."
• "Responsiveness: Agents should respond in a timely fashion to perceived changes in the environment, including changes in the physical world, other agents, or the Internet."
• "Proactiveness: Agents should be able to exhibit goal-directed behaviour."

Agents May Coordinate their Actions

Coalitions

It is possible to automatically allocate the tasks by the formation of coalitions.

A coalition is a group of agents that have decided to cooperate in order to achieve a common task.

Planning in Coalitions

• Calculate coalition values, i.e. determine the values of the possible coalitions in order to choose the preferred ones.

• In an iterated greedy process the agents decide upon the preferred coalitions and form them.

• The benefits of the cooperation may be disbursed among the agents (by fair methods).

• Communication is reduced to agents in the coalition.

Why Mobile Agents?

• They reduce the network load: Distributive systems often rely on communication involving multiple interactions. Mobile agents allow users to package conversation and dispatch it to a place with local communication.

• They overcome network latency: They can better meet real time requirements.

• They encapsulate protocols: They allow for easy upgrades (no legacy problem).

Why Mobile Agents? (Cont'd)

• They execute asynchronously and autonomously.

• They adapt dynamically: They can sense their environment and react.

• They are naturally heterogeneous: They provide optimal conditions for seamless system integration.

• They are robust and fault-tolerant: Mobile agents' ability to react dynamically to unfavourable situations and events makes it easier to build robust and fault-tolerant distributed systems.

Summary

• Agent-based systems play an increasing role in e-commerce, computer games, and other fields.
• Agents form a framework for flexible, robust, proactive computing.
• Agents are realised using a wide variety of tools.

Further Reading    

• P. Maes, R. Guttman, and A. Moukas. "Agents that Buy and Sell: Transforming Commerce as We Know It." Communications of the ACM 42, 3 (Mar. 1999).

  http://xenia.media.mit.edu/~guttman/research/pubs/cacm98.pdf