Transcript mehrdad bibak

‫به نام خدا‬
Multi Robot System
Mehrdad bibak
Multi-Robot Systems
Multi-Robot Systems
Multi-Robot Systems
Multi-Robot Systems
•
•
•
•
•
•
•
Biological Inspirations
Communication
Architectures, task allocation, and control
Localization, mapping, and exploration
Object transport and manipulation
Motion coordination
Reconfigurable robots
Multi-Robot Systems
• Biological Inspirations
– The most common application of this knowledge is in the
use of the simple local control rules of various biological
societies ، particularly ants, bees, and birds، to the
development of similar behaviors in cooperative robot
systems.
– Nearly all of the work in cooperative mobile robotics began
after the introduction of the new robotics paradigm of
behavior based control
– Competition in multi-robot systems, such as that found in
higher animals including humans, is being studied in
domains such as multi-robot soccer.
Multi-Robot Systems
• Communication
– implicit and explicit
– implicit communication occurs as a side-effect of other
actions.
– explicit communication is a specific act designed solely to
convey information to other robots on the team.
– More recent work in multi-robot communication has
focused on representations of languages and the grounding
of these representations in the physical world
Multi-Robot Systems
• Architectures, task allocation, and control
– A great deal of research in distributed robotics has focused
on the development of architectures, task planning
capabilities , and control.
– Three architectures (for Example):
• Linear
• Parallel of linear
• Tree structured
Multi-Robot Systems
Multi-Robot Systems
Multi-Robot Systems
Multi-Robot Systems
Multi-Robot Systems
• Localization, mapping, and exploration
– Almost all of the work has been aimed at 2D environments.
– most of this research took an existing algorithm developed for single
robot mapping ,localization, or exploration, and extended it to multiple
robots.
• Object transport and manipulation
– Enabling multiple robots to cooperatively carry, push, or manipulate
common objects has been a long-standing, yet difficult, goal of multirobot systems.
• Motion coordination
– An advancement in the analysis of motion coordination in multi-robot
teams is the development of provable theorems that characterize the
cooperative performance of team formations under certain conditions.
• Reconfigurable robots
Multi-Robot Systems
Multi-Robot Systems
• Cooperation: situation in which several robots operate
together to perform some global task that either cannot be
achieved by a single robot , or whose execution can be
improved by using more than one robot, thus obtaining higher
performances.
• Awareness: the property of a robot in the MRS to have
knowledge of the existence of the other members of the
system.
• Coordination: cooperation in which the actions performed by
each robotic robot take into account the actions executed by
the other robotic robots in such a way that the whole ends up
being a coherent and high-performance operation.
Multi-Robot Systems
• Centralization: the organization of a system having a robotic
agent (a leader) that is in charge of organizing the work of the
other robots; the leader is involved in the decisional process
for the whole team, while the other members act according to
the directions of the leader.
• Distribution: the organization of a system composed by
robotic agents which are completely autonomous in the
decisional process with respect to each other; in this class of
systems a leader does not exist.
• Strong centralization: centralization in which decisions are
taken by a leader that remains the same during the entire
mission duration.
Multi-Robot Systems
Multi-Robot Systems
• Weak centralization: centralization in which more then one
robot is allowed to become a leader during the mission.
• Direct communication: communication that makes use of
some hard-ware on board dedicated device to signal something
that the other team members can understand..
• Indirect communication
• MRS social deliberation: a system behavior that allows the
team to cope with the environmental changes by providing a
strategy that can be adopted to reorganize the team members'
tasks, so as to use all the resources available to the system
itself to effectively achieve the global goal.
• MRS reactivity: a system behavior in which every single robot
in the team copes with the environmental changes by
providing a specific solution to reorganize its own task in
order to fulfill the accomplishment of its originally assigned
goal.
Multi-Robot Systems
Task Decomposition Methods
1
Task Decomposition Methods
Task Analysis
• A technique for analyzing existing tasks by
observation.
• Doesn’t require understanding of Users’
goals, just what they do.
• But because of that its harder to apply to the
design of a new
system.
– Good for training materials and
documentation
Task Decomposition Methods
Task Analysis: 3 Approaches
• Tasks decomposition: looks at how a task is
split into subtasks and the order in which
these are performed.
• Knowledge-based techniques: what do
users need to know about the objects and
actions involved in a task? How is that
knowledge organized?
• Entity-relation-based analysis: an objectbased approach, identify objects,
relationships and actions.
Task Decomposition Methods
Task Decomposition
• Break the task into subtasks:
• Hierarchical Task Analysis (HTA):
– Organize tasks into a hierarchy
– Include ordering constraints
– Looks something like logic programming
(PROLOG)
Clean house
Get vacuum
cleaner
Clean
hall
Clean
rooms
Clean
living room
Empty
dust bag
Put everything
away
Clean
bedrooms
Task Decomposition Methods
Task Decomposition
0. In order to clean house
1. Get vacuum cleaner out
2. Fix attachment
3. Clean the rooms
3.1 Clean the hall
3.2 Clean the living rooms
3.3 Clean the bedrooms
4. Empty the dust bag
5. Put the vacuum cleaner away
Plan 0: Do 1-2-3-5 in that order
Plan 3: Do any of 3.1, 3.2, and 3.3 in any order depending on
which rooms need cleaning
Task Decomposition Methods
2
Task Decomposition Methods
Task Decomposition
• A divide-and-conquer approach can reduce the
complexity of a task: smaller subtasks require less
capable agents and fewer resources
• The system must decide among alternative
decompositions, if available
• Successful task decomposition depends greatly on a
designer’s choice of operators
• The decomposition process must consider the
resources and capabilities of the robots. Also, there
might be interactions among the subtasks and
conflicts among the robots
Task Decomposition Methods
Task Decomposition Methods
• Inherent (free!): the representation of the problem
contains its decomposition, as in an AND-OR graph
• System designer (human does it): decomposition is
programmed during implementation. (There are few
principles for automatically decomposing tasks)
• Hierarchical planning (robots do it): decomposition again
depends heavily on task and operator representation
Task Decomposition Methods
Task Decomposition Examples
• Spatial decomposition by information source or decision point:
Agent 1
Agent 3
Agent 2
• Functional decomposition by expertise:
Pediatrician
Neurologist
Internist
Cardiologist
Psychologist
Task Decomposition Methods
Task Distribution Criteria
• Avoid overloading critical resources
• Assign tasks to robots with matching capabilities
• Make an robot with a wide view assign tasks to
other robots
• Assign overlapping responsibilities to robots to
achieve coherence
• Assign highly interdependent tasks to robots in
spatial or semantic proximity. This minimizes
communication and synchronization costs
• Reassign tasks if necessary for completing
urgent tasks
Task Decomposition Methods
Task Distribution Mechanisms
• Market mechanisms: tasks are matched to robots by
generalized agreement or mutual selection (analogous to
pricing commodities)
• Contract net: announce, bid, and award cycles
• Multiagent planning: planning robots have the
responsibility for task assignment
• Organizational structure: robots have fixed
responsibilities for particular tasks
• Recursive allocation: responsible agent may further
decompose task and allocate the resultant subtasks
Task Decomposition Methods
3
Task Decomposition Methods
Task Sharing and Result Sharing
• Three stages
•Problem decomposition
• Sub-problem solution
• Solution synthesis
Problem decomposition
• Iteratively hierarchically decompose overall problem into
smaller subproblems until robot can solve them
• Different decomposition levels  different levels of
abstraction
Task Decomposition Methods
Task Sharing and Result Sharing
Problem decomposition
• Important: Decomposition granularity.decomposed problem until sub-
problems are at the level of programming language commands  too fine
grained.  problems with synthesis, management overhead etc. outweigh
decomposition advantages
Sub-problem solution
• Sharing of information during sub-problem solution
Solution synthesis
• may also be hierarchical (respecting different levels of abstraction)
Coordination
• Coordination: Managing inter-dependencies between the activities
of robots
• Examples of inter dependencies:
• 2 people want to go through the same door
• I cannot proceed with my work until you have given your ok
• I make you a copy of an interesting paper without being asked
to do so
• Inter dependencies can be positive or negative
• Positive relationships (benefits for at least one of the robots while
leaving others at least as happy ( pareto-optimality) may be
requested or non requested
Coordination
consumable
resource
resource
non-consumable
resource
negative
interdependencies
incompatibility
positive
requested
(explicit)
nonrequested
(implicit)
Coordination
• Three types of non-requested interdependencies:
• Action-equality-interdependence: Both robots need to have
action a done  one of them can do it
• Consequence-interdependence: Actions of one robot‘s plan have
side effect of achieving other robot‘s goal
• Favour-interdependence: Actions of one robot‘s plan have side
effect of partially achieving other robot‘s goal (positively
contributing to it)
•3 iterated stages:
• each robot decides about his goals, creates local plan
• robots exchange plans to determine interdependencies\\
• robots alter local plans to achieve better coordination
communication Methods
• Black boarding (Strong centralized system)
• Knowledge sharing (Weak centralized system)
• Communicative language (Distributed system)
– Same language
– Different language
– language
• Structure of language
• Type of language
communication Methods

•Message
Blackboard

information available for all

no direct communication

simple architecture
robot
robot
robot
–direct exchange
–common language
–conversation - sequences
of messages
robot
Blackboard
robot
robot
robot A
(Sender)
Message
robot B
(Receiver)
communication Methods
• Consider:
– performative = request
content = “the door is closed”
speech act = “please close the door”
– performative = inform
content = “the door is closed”
speech act = “the door is closed!”
– performative = inquire
content = “the door is closed”
speech act = “is the door closed?”
communication Methods
(Request
:Sender
sender1
:Receiver
receiver1
:Language
KIF/FIPA
:Ontology
Ontology1
:Reply-With 1
:Content content1
communication Methods
• We now consider robot communication
languages (ACLs) — standard formats for the
exchange of messages
• The best known ACL is KQML, developed by
the ARPA knowledge sharing initiative
KQML is comprised of two parts:
– the knowledge query and manipulation language
(KQML)
– the knowledge interchange format (KIF)
communication Methods
• KQML is an ‘outer’ language, that defines
various acceptable ‘communicative verbs’, or
performatives
Example performatives:
–
–
–
–
ask-if (‘is it true that. . . ’)
perform (‘please perform the following action. . . ’)
tell (‘it is true that. . . ’)
reply (‘the answer is . . . ’)
• KIF is a language for expressing message
content
communication Methods
• “The temperature of m1 is 83 Celsius”:
(= (temperature m1) (scalar 83 Celsius))
• “An object is a bachelor if the object is a man
and is not married”:
(defrelation bachelor (?x) :=
(and (man ?x) (not (married ?x))))
• “Any individual with the property of being a
person also has the property of being a
mammal”:
(defrelation person (?x) :=> (mammal ?x))
communication Methods
• In order to be able to communicate, robots must have
agreed on a common set of terms
• A formal specification of a set of terms is known as an
ontology
• The knowledge sharing effort has associated with it a
large effort at defining common ontologies — software
tools like monolingual for this purpose
• Example KQML/KIF dialogue…
A to B: (ask-if (> (size chip1) (size chip2)))
B to A: (reply true)
B to A: (inform (= (size chip1) 20))
B to A: (inform (= (size chip2) 18))