Introduction to AI - Week 10 Agents Reactive Systems - Rational Agents * Reactive Systems: (as antithesis to classical AI): no explicit representation of knowledge, simple reactive code exhibits complex seemingly intelligent behaviour. * Rational Agents: Proactive software systems with agenda of their own. _________________________________________________________________________________________________________ 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 Herbert - a robot to find soda can-like objects: * 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. That is, the planner knows the policy and explores the search space searching in the policy first. Then: Performance of rfs is monotonically increasing. _________________________________________________________________________________________________________ Example Scenario maze.jpg] 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 The concept "agent" is very wide and its usage varies. It may mean: * 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 Russell-Norvig: An Agent is anything that perceives its environment through sensors and acts upon that environment through effectors. 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 russell-norvig-learning-agent.jpg] _________________________________________________________________________________________________________ A General Agent Architecture by A. Sloman sloman-arch.jpg] _________________________________________________________________________________________________________ Characteristics of Intelligent Agents [Shaun Abushar, Naoki Hirata] * "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 Assume a set of agents, which make plans. and a centralised coordinator which negotiates with agents about how to coordinate their distributed plans. plan-coord.jpg] _________________________________________________________________________________________________________ Coalitions Example: Assume a transportation task of delivering 10,000 flowers from New Jersey to New York City. The task may be performed by several trucks or by a single helicopter, a lift-truck is necessary in both cases. A coalition of trucks and lift-trucks will probably be cheaper than a coalition of a helicopter and lift-trucks. 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? [Danny B. Lange and Mitsuru Oshima 1999] * 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 books-shelf1.jpg] There is a lot of material on-line, e.g. * 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). [1]http://xenia.media.mit.edu/~guttman/research/pubs/cacm98.pdf _________________________________________________________________________________________________________ _________________________________________________________________________________________________________ © Manfred Kerber, 2004, Introduction to AI 22.12.2004 The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l10.html. URL of module [2]http://www.cs.bham.ac.uk/~mmk/Teaching/AI/ References 1. http://xenia.media.mit.edu/~guttman/research/pubs/cacm98.pdf 2. http://www.cs.bham.ac.uk/~mmk/Teaching/AI/