1. Artificial Intelligence: from Knowledge to Behavior Based
2. Review of some formative papers
3. Lego: My History
4. Machine Learning and Adaptation
5. Multiple Agents and Collectives
6. Some Things for the Theory-guys
7. Useful Publications and Resources

In the 1980's a number of researchers began developing what is now called:

Rodney A. Brooks is the progenitor of BBAI.

We have a couple of his other papers online here:

• The Behavior Language -- Description of the language he developed.
• Intelligence Without Reason -- Non-von (Neumann).

1991 -- Theme setter for the first adaptive learning conference. Proposal for taxonomy and development of "artificial animals" that can survive on their own and build competency from the ground up.

1993 -- Short and to the point insider's overview of the field, contrasted with traditional Knowledge Based AI . Good analysis of the strengths and pitfalls of both.

1991 -- Using plans as resources, not 'infallable' programs. Develops the idea of a flow gradient to direct the robot. The gradients can be modified on the fly depending on circumstances

Ronald C. Arkin, Georgia Institute of Technology
        Integrating Behavioral, Perceptual, and World Knowledge in Reactive Navigation

1991 -- Describes schemas as ways to represent fundamental operations and then generate gradient paths for the robot to follow.

Behavior Based Robotics

1998  -- Excellent review up to mid 1990's.

Luc Steels, Vrei Universiteit Brussel
        Towards a Theory of Emergent Functionality

1991 -- Using distributed, rather than hierarchical, control mechanisms that rely on direct feedback from the environment leads to the emergence of behaviors that are not explicitly programmed. Applies most of the basic dynamical systems theory to Behavior Based Robotics. References Prigogine twice.

Maja J. Mataric, MIT (USC now)
        Navigating with a Rat Brain

1990 -- Biological analogy with the cognitive maps in the rat hippocampus being used to navigate in preference to visual ques. Applied to a real robot, the mechanism uses a topological "map".

Leslie P. Kaelbling, Stanford
        Foundations of Learning in Autonomous Agents

1993 -- Finite state machine theory, including probabilistic state machines. Apparently was not aware of our little Korner of Kaos.

Toys from Industry: Lego

• Edinburgh University -- photo and block diagram .
• Vrije Universiteit Brussel -- photo .
• MIT:

  • Mitchel Resnick -- 1989;
           Lego, Logo, and Life
                   in C. Langton - Artificial Life
  • Fred Martin, etal -- 1990;
            BraitenBerg Bricks: A Lego-Based Creature Construction Kit
                   delivered at the second Artificial Life Conference, SFI
    

Machine Learning and Adaptation

The absolute basics:

1992 -- Again, the Edinburgh guys have a good idea: A very simple learning system .

Reinforcement Learning

1995 -- Haven't absorbed it.

1998 -- Standard text on the subject.

Finite State Automata -- TBD

Q-Learning -- TBD

Classifier Systems -- TBD

Neural Nets -- TBD

Genetic Algorithms -- TBD

Multiple Agents and Collectives

Distributed Artifical Intelligence (DAI)

Keith S. Decker, Distributed Problem Solving: A survey (1987)
(I couldn't get it from the durn IEEE because their archive only goes to 1988...)
Divides the arena into four dimensions:

1. Agent Granularity -- Degree of independence between agents.
2. Heterogeneity -- How different are individual agents.
3. Control Mechanism -- Hierarchical vs. distributed, competitive vs. cooperative, etal.
4. Communication -- None to unlimited, broadcast vs. agent-to-agent, high vs. low level.

MAS

Nicholas R. Jennings, etal, Queen Mary and Westfield, CMU
        A Roadmap of Agent Research and Development

1998 -- A large review paper that defines the various branches and challenges in the field. They define agent to be distinct from 'helper' programs such as xbiff [paraphrased]:

• Situated -- Existing in and directly sensing a specific environment.
• Autonomous -- Having control over it's own actions and internal state.
• Flexible -- A three part set of abilities:
  • Responsive -- Responding to stimulus in a 'timely' fashion.
  • Pro-active -- Taking initiative when appropriate (...err...hmm?).
  • Social -- Interacting with other agents and humans.

Gerhard Weiss (ed)
        Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence

2000 -- Haven't read anything but the introduction yet....but, curiously, MIT is not represented in the authors...

The challenges he delineates for DAI generally arise from the micro-macro problem, i.e., the relationship between individual agents and their social environment:

• Goal and task decomposition and result re-synthesis;
• Communication languages and protocols;
• Adaptively balancing communication with local computation;
• Representing and reasoning about other agents;
• Measuring and improving agents' coordination efforts;
• Forming ad hoc organizational structures as needed;
• Negotiating, contracting, and conflict resolution;
• Mitigation of 'under-damped' behaviors;
• Engineering development platforms and frameworks;
• Formal descriptions of MAS.

Peter Stone and Manuela Veloso, ATT, CMU
        Multiagent Systems: A Survey from a Machine Learning Perspective

2000 -- A huge, readable, paper with pages of useful references up until the year 2000. They apply the Decker taxonomy to robotic systems along two axes and then describe typical uses and problems for each quadrant of the graph:

1. Heterogeneity -- From all the same beastie to completely different capabilities and sophistication levels.
2. Communication -- From only what can be directly observed to broadband transmission.

Their scheme allows the Control Mechanisms to vary from totally independent to the moral equivalent of a single agent with one decision making process (of course, depending on the communication axis).

In any of the quadrants the quality of the agents' interactions can be placed on a scale from cooperative to antagonistic. Their cannonical example of MAS behavior is a Preditor-Prey game which involves agents on both ends of this scale.

The paper points out a number of areas for further research (as of 1999-2000 anyway):

• Credit Assignment -- Did my action really make a difference or did something else change?
• Learning to Cooperate and Share Resources -- Determine what actions are collectively useful and select for them in individuals. Also need to be able to share resources, even to the detriment of individuals.
• Evolving Language -- Agents develop their own language to suit their own purposes.
• The Utility of Communication -- Is it better to keep quiet? When?
• Information Reliability and Trust -- How much do you believe and trust each individual? What happens when contracts are broken?

Their not-hidden agenda is to promote Robotic Soccer as a better development arena for MAS.

Pedro Lima, etal, Lisbon Technical University, Georga Tech, etal
        Robo-Cup 2001

2002 -- This is a seemingly frivolous description of the annual IEEE sponsored robot soccer tournament. They even have a division for Eibo Sony-dogs. However the principles behind the play cut to the core of  MAS behaviors and many papers are delivered and software shared amongst competitors (almost all are university engineering/CS classes). [see pages 4 and 9]

They are also starting a Robot Search and Rescue competition. [see page 3]
Just for schadenfreude or something similar, here's the Utah State entry, a modified radio control car....which successfully found victims but failed to communicate their locations and thus was eliminated from competition.

Sample MAS Work

C. Roland Kube & Hong Zhang , University of Alberta
        Collective Robotic Intelligence

1993 -- Box pushing robots cooperate by simply not interfering with each other.

Maja J. Mataric, MIT (now USC)
        Learning to Behave Socially

1994 -- Learning to cooperate by "vicariously" sharing behavior rewards.

Cao, Y. Uny, etal, UCLA, Caltech
        Cooperative Mobile Robotics: Antecedents and Directions

2000 -- Yet Another Massive Review paper....more references...specifically Asian authors?

Robert Grabowski, etal, CMU
        Heterogeneous Teams of Modular Robots for Mapping and Exploration

2000 -- Describes small home-brew robots with differing capabilities that work in groups ( Millibots , developed at CMU). Need to study this one.

2000 -- Using a hierarchy of knowledge of neighbor robots to limit state space. The further away the neighbors are, the less you need to remember about them.

2000 -- Using multiple robots to increase their localization accuracy by sharing relevant information.

Robin R. Murphy, etal , University of South Florida
        Emotion-Bassed Control of Cooperating Heterogeneous Mobile Robots

2002 -- Describes a two robot system where each perform different tasks that require a rendevous. The 'emotional' content is how confident they are that the rendevous will be on schedule. Given their emotional states, the 'bots can modify their behavior to accomplish their tasks.

S.S. Ge & Y.J. Cui, National University of Singapore
        Dynamic Motion Planning for Mobile Robots Using Potential Field Method

2002 -- Tracking a moving target with moving obstacles, simulated and real 'bots. [see page 14]

Some Things for the Theory-guys:

• George Kiss chaos paper: Autonomous Agents, AI and Chaos Theory (1991)
• L. Kaelbling FSA paper: Foundations of Learning in Autonomous Agents (1993)
• Tucker Balch infoTheory: Hierarchic Social Entropy: An Information Theoretic Measure of Robot Group Diversity (2000)

Useful Publications and Resources

Books and Collections

Vehicles: Experiments in Synthetic Psychology, 1984; Braitenberg, V. -- Fun thought experiments you can now do with the Lego Mindstorms kit.

Designing Autonomous Systems, 1990; Maes, P. (ed) -- Reprints from journal Robotics and Autonomous Systems, vol 6.

From Animals to Animats #1,2,3, 1991,3,4 -- Proceedings of the first three International Conferences on Simulation of Adaptive Behavior, many interesting papers in each issue.

Toward Learning Robots , 1991 -- Reprints from journal Robotics and Autonomous Systems, vol 8.

Reinforcement Learning , 1998; R.S. Sutton & A.G. Barto -- Standard text.

Multiagent Systems , 2000; G. Weiss (ed) -- Collected papers on MAS.

Proceedings of the First International Conference on Multi-Agent Systems, 1995, AAAI -- Formative work.

Adaptation, Coevolution, and Learning in Multi-Agent Systems, 1996; AAAI spring symposium.

Adaptation and Learning in Multi-Agent Systems, 1996; Weiss and Sen -- TBA.

An Introduction to AI Robotics, 2000; Murphy, R. -- On order.

Robot Teams: From Diversity to Polymorphism, 2002; Balach and Parker -- Ordered

Journals

IEEE {Journal of, Transactions on} Robotics and Automation --
http://ieeexplore.ieee.org/Xplore/DynWel.jsp

Autonomous Robots --
http://www.kluweronline.com/issn/0929-5593/current

Machine Learning --
http://www.kluweronline.com/issn/0885-6125/current

Autonomous Agents and Multi-Agent Systems --
http://www.kluweronline.com/issn/1387-2532/current

Robotics and Autonomous Systems --
http://www.sciencedirect.com/science

And, of course...