Sistemi per il Governo dei Robot

Sistemi per il Governo dei Robot

Silvia Rossi - Lezione 22

Objectives

• List and describe the dimensions of a multi-agent system:

heterogeneity, control regime, cooperation, and goals

• List and describe the axes for describing a MAS task (time, subject of action, movement, dependency)

• List and describe the axes for describing a MAS collective (composition, size, communications, reconfigurability)

• Given a description of an intended task, a collection of robots, and the permitted interactions between robots, design a multi-

agent system and describe the system in terms of heterogeneity, control, cooperation, and goals.

Objectives (cont.)

• Compute the social entropy of a team.

• Be able to program a set of homogeneous reactive robots to accomplish a foraging task.

• Describe the use of social rules and internal motivation for emergent social behavior.

• Be able to diagram the steps of robots in a team using Mataric’s social rules

Objectives (cont.)

• Given a layout of robots and tasks and a table such as Fig. 8.6 partially filled in, be able

– Fill in the change in impatience and acquiescence

• Given a layout of robots and tasks and a table such as Fig. 8.6 with t₀ through t_n:

– show the next two moves and corresponding changes to the level of

impatience and acquiescence of each task and the task list for robots in a team using ALLIANCE

What we (should) got so far…

Robot:

In a real environemt

Able to perceive and act Able to think

ENVIRONMENT

Why Multi-robot?

Why Multi-robot?

Some tasks require a team

Why Multi - robot?

Some tasks require a team [video]

Why Multi-robot?

Faster execution

Some tasks may be decomposed ad divided in order to be executed more efficiently

Mapping of a big area

Why Multi-robot?

Faster execution

Some tasks may be decomposed ad divided in order to be executed more efficiently

Mapping of a big area

Why Multi-robot?

Costs

More specialist robots are preferred to a single generalist one

Simpler design

Why Multi-robot?

Failure robustness is increased by the number of robots and the replication [video]

Why Not Multi-robot?

Coordination

Communication Test difficulties N x Problem

The Study of Multiple Robots

DISTRIBUTED ARTIFICIAL INTELLIGENCE

DISTRIBUTED PROBLEM

SOLVING

MULTI- AGENT SYSTEMS

The Study of Agency

(after Stone and Veloso 2002)

DISTRIBUTED ARTIFICIAL INTELLIGENCE

DISTRIBUTED PROBLEM

SOLVING

MULTI- AGENT SYSTEMS

HOW TO SOLVE PROBLEMS

OR MEET GOALS BY

“DIVIDE AND CONQUER”

SINGLE COMPUTER:

• HOW TO DECOMPOSE TASK?

DIVIDE AMONG AGENTS:

•WHO TO SUBCONTRACT TO?

4 Dimensions of a Multi-agent System

• Heterogeneity

– Same (homogeneous) vs. different (heterogeneous) – Can be different on either software or hardware

• Control Regime

– Centralized (Phantom Menance) vs. Distributed

• Cooperation

– Active (acknowledge each other) vs. Non-active (cooperation emerges, not explicit)

– Communicating or non-communicating

• Goals

The Ecological Niche of a Multi-Agent System

Remember….

• Single Robot

–Task

–Environment –Agent

The Ecological Niche of a Multi-Agent System

• Multi-agent system

–Task

–Environment

–Individual Agent –Collective

EMPHASIS

MAS Ecological Niche: Task

(after Balch 02)

• There are 4 axes of a MAS Task

–Time

–Subject of Action –Movement

–Dependency

4 Categories of Time

1. Fixed time

– ex. Collect as many cans in 10 minutes

2. Minimum time

– ex. Visit all rooms as fast as possible (minimize the time)

3. Unlimited time

– ex. Patrol the building

4. Synchronization required

– ex. Push two buttons at same time

Class Question

• Consider the task of humanitarian demining–

clearing a complex terrain of land mines- with robots.

• This task falls into what category of time?

– Fixed

– Minimum – Unlimited

– Synchronized

2 Categories of Subject of Action

Subject of Action:

–Object-based

• robots place a single object- ex. soccer

–Robot-based

• robots place themselves- ex. mapping

Class Question

• Consider the task of humanitarian demining–

clearing a complex terrain of land mines- with robots.

• This task falls into what category of time?

– Object-based – Robot-based

4 Categories of Movement

1. Coverage

– Spread out to cover as much as possible

2. Convergence

– Robots meet from different start positions

3. Movement-to

– Going to a single location

4. Movement-while

Class Question

• Consider the task of humanitarian demining–

clearing a complex terrain of land mines- with robots.

• This task falls into what category of time?

– Coverage

– Convergence – Movement-to

3 Categories of Dependency

1. Independent

– Robots don’t have to work directly or be aware of others

2. Dependent

– Must work together for efficiency ex. Box pushing

3. Interdependent

– Cyclic dependency ex. resupply

Box-Pushing

MAS Task Summary

• Time

– Fixed time task (ex. Collect as many cans in 10 minutes) – Minimum time (ex. Visit all rooms as fast as possible) – Unlimited time (ex. Patrol the building)

– Synchronization required (ex. Push two buttons at same time)

• Subject of Action

– Object-based (e.g., robots place a single object- soccer) – Robot-based (e.g., robots place themselves- mapping)

• Movement

– Coverage (ex. Spread out to cover as much as possible) – Convergence (ex. Robots meet from different start positions) – Movement-to (ex. Going to a single location)

– Movement-while (ex. Formation control)

• Dependency

– Independent (ex. Doesn’t require agents to know about others) – Dependent (ex. Task requires multiple agents)

Class Question

• Consider the task of search and rescue, where multiple robots are to be used to search a

collapsed building.

• Describe the task in terms of the 3 axes of a collective task

– Time

– Subject of action – Movement

Class Question

• Consider the task of forensic sampling, where robots are to enter the floor a building where a

crime has been committed, and then photograph and scan the entire floor as accurately as possible.

• Describe the task in terms of the 3 axes of a collective task

– Time

– Subject of action – Movement

MAS Ecological Niche:

Collective

There are 4 axes of a collective:

–Composition

–Size of the collective –Communication

–Collective reconfigurability

2 Categories of Composition

• Composition

–Homogeneous –Heterogeneous

Case Studies

• Georgia Tech 1994 AAAI Mobile Robot Competition team

• Each robot hardware and software homogeneous

• Reactive behaviors

– Wander-for-goal – Move-to-goal – Avoid

– Avoid-other-robots – Grab-trash

– Drop-trash

• Affordances

– Orange=goal

DIMENSIONAL SCORE:

HOMOGENEOUS

DISTRIBUTED CONTROL

ACTIVE COOPERATION (THOUGH MINIMAL)

Example of Heterogeneous Team

• USF USAR team

• Robot had different hardware, software

• Currently teleoped

navigation with autonomous reactive victim detection

• Single goal, active cooperation

– Confirm a victim with distributed sensors

– Open door, “spotting” for

navigation in confined spaces

DIMENSIONAL SCORE:

HETEROGENEOUS

DISTRIBUTED CONTROL (COULD BE CENTRAL.)

ACTIVE COOPERATION SINGLE GOAL

Social Entropy

• Way to measure heterogeneity of a collective

• (go to board-> 4 identical, 4 marsupial)

4 Categories of Size

• Size of the collective

–Alone –Pair

–Limited

• n<<than size of task or environment

–Infinite

• n>>than size of task or environment)

3 Categories of Reconfigurability

• Collective reconfigurability

– Static

• The organization doesn’t change, no matter what

– Communicated

• Coordinated rearrangement

• Ex. Ordered to change formation

– Dynamically

• Changes arbitrarily (esp. due to failure)

Box Pushing: Dynamic Reconfigurability

Communication

Cooperation between robots can be achieved by communication mechanisms and the

exchange of messages.

Direct and indirect communication.

Communication

Direct communication makes use of dedicated hardware

Indirect communication makes use of stigmergy

Can reduce complexity in the design of large scale systems

5 Categories

– Infinite

• comms are free

– Motion

• costs as much to communicate as it would to move

– ex. Box pushing (if other robot can feel the box, it’s comms)

– Low

• comms costs more than moving from one location to another

– Zero

• no communication between agents

What Do Robots Say to Each Other?

• How do they “talk”?

– Implicit: signaling, postures, smell – Explicit: language

• Who does the talking?

– “the boss” -Centralized control – Everybody - Distributed control

What do Robots Say?

(after Jung and Zelinsky 02)

• Communication without meaning preservation

– Emitter can’t interpret its own signal

– Receiver reacts in a specific way (stimulus-response) – Ex. Mating displays, bacteria emit chemicals

• Communication with meaning preservation

– Shared common representation

– Ex. Ant leaves pheromone trail to food, itself & peers can follow

Summary: Collective

• Composition

– Homogeneous, Heterogeneous

• Size of the collective

– Alone, Pair, Limited, Infinite

• Communication

– Infinite- comms are free

– Motion – costs as much to communicate as it would to move

– Low – comms costs more than moving from one location to another – Zero – no communication between agents

– Topology

• Broadcast, address, tree, graph

• Collective reconfigurability

Class Exercise

• Consider the case of resupply, where many multiple vehicles are in the field and a lesser number of

smaller vehicles exist to carry fuel to them, return to base, and then carry more fuel out on demand. A

field vehicle emits a message that it needs to be

refueled. The message intensity increases inversely proportional to the amount of remaining fuel.

• Describe the MAS task.

In the end…most popular

• Homogeneous Non-communicating agents

• Heterogeneous Non-communicating agents

• Homogeneous communicating agents

• Heterogeneous communicating agents

Class Exercise

• Design a multi-agent team for USAR in terms of

– Heterogeneity – Control

– Cooperation – Goals

Coordination

Coordination problems are present both in artificial and natural systems.

Examples from nature:

Cooperation taxonomy

COOPERATION

Cooperation

The ability of a group to cooperate in order to achieve a common goal.

We can distinguish among cooperative and competitive systems.

A pure cooperative system has a single shared goal among the agents.

Cooperation taxonomy

AWARE UNAWARE

COOPERATION

Knowledge

Represents the ability of a the robots to have information about the rest of the group.

Aware: robots are aware of the team metes

Unaware: robots acts without considering their team mates

Frequently inspired by biological domains

Easier to manage from the engineering point of view

Knowledge is not equal to communication: robot can manage the presence of other robots without the necessity to communicate with them.

Cooperation taxonomy

AWARE UNAWARE

COOPERATION

STRONG

COORDINATION

WEAK

COORDINATION

NO

COORDINATION

Coordination levels

We talk about coordination when, before acting, the robot takes into account other robots

actions in order to have a coherent global behavior.

There are different methods to take into account other robots actions.

An interaction protocol is defined as a set of rules that robots have to follows in order to interact.

May require a subdivision in different roles.

According to the protocol we can classify different coordination mechanisms.

Coordination

What kind of coordination?

What kind of coordination? a b

Cooperation taxonomy

CENTRALIZED WEAK DISTRIBUTED

AWARE UNAWARE

COOPERATION

STRONG

COORDINATION

WEAK

COORDINATION

NO

COORDINATION

Organization and Control

How, in a group of robots, decisions take place?

Main distinction among centralized and distributed control.

Centralized

A single system takes decision for the group

Potentially optimal

Coordination may be implicit – Difficult management

– Single point of failure – Slow reaction time.

Distributed

Each robots takes decision according to its knowledge

Simple and quick

Multiple simultaneous tasks - Explicit coordination

Coordination

WEAK COORDINATION STRONG COORDINATION

 SUB-TASKS DECOMPOSITION

 PARALLEL EXECUTION

 MINOR INTERACTION

 STRATEGIES TO DECOMPOSE AND ALLOCATE TASKS ARE NEEDED.

 NOT DECOMPOSABLE TASKS

 COORDINATED EXECUTION

 STRONG INTERACTION

Tasks for multi-robot teams

Mapping and exploration Target tracking

Inspection WEAK COORDINATION

Tasks for multi-robot teams

Object transportation Robot soccer

Large-scale construction Coordinated exploration

ROBOTIC

CONSTRUCTION.

STRONG COORDINATION

Trasporto di oggetti

Working with objects

Flocking

Human-robot Coordination

Human-robot Coordination

How to Get

“Right” Emergent Behavior

• Societal Rules vs. behaviors

– Nerd Herd, Maja Mataric

• What if homogeneous, individual goals operating in the same area?: example-- traffic and traffic jams

• Motivation

– ALLIANCE, Lynn Parker

• What if have single goal, divided among homogeneous agents and one robot breaks?:

example—cleaning up a nuclear spill

Explicit Social Rules vs. Behaviors

• Societal Rules

– Ignorant Coexistence

• Basic reactive approach, except robots couldn’t recognize other robots

• High degree of task interference

– Informed Coexistence

• Recognize each other PLUS simple social rule: if detect robot, stop and wait P; if still there, turn left then resume move to goal

• Better

– Intelligent Coexistence

• Recognize each other PLUS behavior: repulsed by other robots concurrent with attraction to move in same direction as the majority

Mataric’s Nerd Herd and Social Rules

Motivation: ALLIANCE

• Divide and conquer works until a robot fails; then what about the failed robot’s area

• Robot A fails:

– It may realize that its not doing a good job: becomes increasingly

FRUSTRATED and change behavior (give up) called ACQUIESCENCE

• Allows other robots to help without task interference

– It may be clueless

• Other robots can help, but not as efficiently

• Robot B is finished with its task

– Sees that waiting on Robot A, and becomes increasingly FRUSTRATED

ALLIANCE

Summary

• Many, cheap robots is often better than single, expensive robot

• Multi-agents are generally at least reactive, sometimes hybrid deliberative/reactive

• Dimensions for categorizing:

– Heterogeneity, control, cooperation, and goals – (may change dynamically)

• Interference is a big problem

– Social rules

Review Questions

• What are the dimensions of a multi-agent system?

– Heterogeneity, control regime, cooperation, goals

• What are the four axes of a task in a collective?

– time, subject of action, movement, dependency

• What are the four axes of a collective?

– composition, size, communications, reconfigurability

• Which is more likely to fail to in the field?

The Coordination Problem

Managing the interdependencies between the activities of agents. e.g.

You and I both want to leave the room. We independently walk towards the door, which can only fit one of us. I graciously

permit you to leave first.