Transcript PPT
Introduction to Multiagent Systems Mohsen Afsharchi An Agent An agent is anything that can perceive its environment through sensors and act upon that environment through actuators An agent that always tries to optimize an appropriate performance measure is called a ‘rational agent’. Human agents (eyes as sensors, hands as actuators) Robotic agents (cameras as sensors, wheels as actuators) Software agents (a graphical user interface as sensor and as actuator) Multiagent Systems A system that consists of a group of agents that can potentially interact with each other. The corresponding subfield of AI that deals with principles and design of multiagent systems is called distributed AI. Software agents on the Internet Soccer playing robots Characteristics of MASs Agent Design Heterogeneous, different hardware or implement different behaviors. Homogeneous, designed in an identical way and have a priori the same capabilities. Environment Static, easier to handle and allow for a more rigorous mathematical treatment. Dynamic, presence of multiple agents makes the environment appear dynamic Characteristics… Deterministic vs. Non-deterministic, Do actions have guaranteed effect? Discrete vs Continuous, Is the number of actions and percepts finite? (Does it matter?) Perception Distributed, Spatially ; Temporally; Semantically Observable, Partially or Full Sensor fusion Characteristics… Control Typically Decentralized. General problem of multiagent decision making is the subject of Game theory Collaborative or Team MAS where the agents share the same interests Distributed decision making needs appropriate Coordination mechanisms Characteristics… Communication for coordination among cooperative agents for negotiation among self-interested agents Ontology Language Knowledge Cooperative agents Competitive agents Common knowledge Application Speedup and efficiency, due to the asynchronous and parallel computation. Robustness and reliability, in the sense that the whole system can undergo a ‘graceful degradation’ when one or more agents fail. Scalability and flexibility, since it is easy to add new agents to the system. Cost, assuming that an agent is a low-cost unit compared to the whole system. Development and reusability, since it is easier to develop and maintain a modular system than a monolithic one. Applications The Semantic Web; Web services are just the start. Automated manufacturing. [Baker et al., 1999] [Huhns et al., 2002] Distributed sensor fusion. [Vidal, 2003] [Scerri et al., 2002] [Ortiz and Rauenbusch, 2002] Dynamic resource allocation (who does what). [Mailler et al., 2003] Supply-chain automation. [Singh and Huhns, 1999] Coordination of robots: Mars colonization. [Pirjanian et al., 2000] Any application where independent localized units must coordinate to achieve some desired system behavior. Challenging Issues How to decompose a problem, allocate subtasks to agents, and synthesize partial results. How to handle the distributed perceptual information. How to enable agents to maintain consistent shared models of the world. How to implement decentralized control and build efficient coordination mechanisms among agents. How to design efficient multiagent planning and learning algorithms. Challenging Issues How to represent knowledge. How to enable agents to reason about the actions, plans, and knowledge of other agents. How to enable agents to communicate. What communication languages and protocols to use. What, when, and with whom should an agent communicate. How to enable agents to negotiate and resolve conflicts. How to enable agents to form organizational structures like teams or coalitions. How to assign roles to agents. How to ensure coherent and stable system behavior. An Agent: Abstract Architecture c Agent Model I Perception a Agents with State a Rational Decision Making Assuming a discrete set of time t 0,1,2,..., in each of which the agent must choose an action a t from a set of actions A To optimally choose an action at time t , it must use its complete history of observation and action a for t Mapping function is called the Policy of the agent (0 , a0 ,1 , a0 ,...,t ) at An agent that is simply ignoring the past is called a reflect agent and its policy is called reactive or memory-less (t ) at in a Markov world an agent can safely use the memory-less policy for its decision making, in place of the memoryexpensive policy. State and Observability The collective information that is contained in the world at any time step t , is called a state of the world and denoted by Discrete world : characterized by a finite number of states, Continuous world Observable world Partially Observable world (stochastic observation model) Stochastic World… More on Observability Noise : e.g. Sensor malfunction Perceptual Aliasing : different states may produce identical observations to the agent at different time steps. In other words, two states may ‘look’ the same to an agent, although the states are different from each other. Deterministic world : Stochastic world : Utility Maximizing Agents A goal is just a preference over certain states. Utility function U(s) is the utility of state for the agent. The agent in should take the action which maximizes its expected utility The function that implements this choice is the policy. In this case Optimal Action-Value function Example A toy world Unlike path planning in a deterministic world that can be described as graph search, decision making in stochastic domains requires computing a complete policy that maps states to actions. (Reinforcement Learning) Deductive Reasoning Agent Counterpoint: Rodney Brooks believes that the world should be its own model Agents as Theorem Prover w Action Selection Function Pragmatics Building a purely logical agent is impractical. Proving theorems in first-order predicate logic is slow. Late actions are based on old information. But, webservice description languages are built to be used by logical agents. There might be a new renaissance of logical approaches. For example, OWL-S uses service profiles which define services in terms of their Inputs, Outputs, Pre-conditions. Agent Oriented Programming Program agents in terms of mentalistic notions. Pre-cursor to a lot of important work in agent research. The hope is that using these abstractions would simplify the programming of agents. Introduced by Yoav Shoham in 1990. The idea was then implemented as AGENT0 [Shoham, 1991]. Not used anymore. AOP Primitives An agent has Capabilities things it can do. Beliefs Commitments things it means to do. Commitment rules that tell it when to create or drop a commitment. The commitment rules have a message condition and a mental condition (both in the conditional part). An agent can take a private action which amounts to running a subroutine, or a communicative action which amounts to sending a message. Messages are limited to: requests, unrequests, and inform messages. Agent0 Example I If I receive a message from agent which requests for me to do action at time and I believe that agent is a friend. I can do action at time, I am not committed to doing any other action. then commit to doing action at time. Going the Wrong Direction? Deduction is slow. Deduction is complicated. Maybe, rationality requires an environment! Maybe, intelligent behavior emerges from the interaction of simple behaviors [Minsky, 1988]. Elephants Do not Play Chess !! But? What is Intelligence? Is a house fly intelligent? A house fly is much simpler than most of our attempts at artificial intelligence For example… It is unlikely that a house fly: Forms 3D surface descriptions of objects Reasons about the threat of a human with a fly swatter, in particular about the human’s beliefs, goals, or plans Makes analogies concerning the suitability for egg laying between dead pigs Constructs naïve physics theories of how to land on the ceiling Real Intelligence!!! It is much more likely that a house fly: Has close connection of sensors to actuators Has pre-wired patterns of behavior Has simple navigation techniques Functions almost as a deterministic machine And yet a house fly is much more successful in the real world than our attempts at AI Hey Rodney! Proposed by Brooks in [Brooks, 1986]: for robots. Extended it into a new view of AI,[Brooks, 1991a, Brooks, 1991b]. Key ideas: Intelligent behavior does not require explicit representations. Intelligent behavior does not require abstract (symbolic) reasoning. Intelligence is an emergent property of certain complex systems. A New Architecture Follow the evolutionary path of intelligence Start with simple intelligence After a successful design, extend to higher levels of intelligence Easier to implement than human intelligence Robust design as higher intelligence levels can fail but the lower levels will still work After all, there are plenty of examples of successful intelligence in nature that are much simpler than many AI research areas (the house fly example) The Subsumption Architecture The Subsumption Architecture is: A layering methodology for robot control systems A parallel and distributed method for connecting sensors and actuators in robots An Example: Allen Brooks’ first Subsumption robot Level 0: Runs away if approached, avoids objects Allen… Levels 1 and 0: Adds wandering Subsumption Implementation The agent has a set of behaviors which are purely reactive (action: S A). Many of them can fire at the same time. We choose an action using the subsumption hierarchy. Behaviors are arranged into layers, so that lower layers inhibit higher one. The lower layers have the higher priority. Formally, a Action Selection Limitations Agents must have enough information in local environment to determine which action to take. How to take into account old or non-local information? How do reactive! agents learn? Emergence (between agent and environment) is hard to engineer. We don’t have a methodology. It is very hard to build agents that have many behaviors. On the plus side, it has been a very successful method for building robots, such as Roomba.