Lecture 5: Intelligent Control, Part 2
Lecture 5: Intelligent Control, Part 2
Elizabeth Sklar
Department of Informatics
King’s College London
23 October 2018
(version 1.0)
1 / 111
Outline
Today
Navigation
Cognition
Behaviour-Based Systems
Multi-Robot Systems
2 / 111
Today: Intelligent Control, Part 2
I Navigation
I Cognition
I Behaviours
I Multi-Robot Systems
3 / 111
Outline
Today
Navigation
Cognition
Behaviour-Based Systems
Multi-Robot Systems
4 / 111
What counts as navigation?
I Navigation is concerned with how a robot gets around the
world.
I Navigation is more than just blundering about using dead
reckoning.
I We assume that the robot:
I Knows where it is.
I Knows where it is going.
I We are concerned with getting the robot from one place to
another.
5 / 111
Navigation
I We distinguish between two kinds of navigation:
I Global navigation
I Local navigation
6 / 111
Navigation, p2
I Global navigation is about deciding how to get from some
start point to a goal point.
I The robot plans in some sense.
I We will look at methods for path planning.
I In short, the robot comes up with something like a “plan” — a
series of steps — to get it from its current location to its goal.
I The “plan” is typically a sequence of waypoints.
I We will look at some different methods that are appropriate
for different map representations.
I Remember them?
7 / 111
Navigation, p3
I Local navigation is about obstacle avoidance.
I If there are objects in the way, make sure the robot does not
hit them.
I There are a range of different approaches depending on what
kind of information the robot has about the world.
I Depends on sensors
8 / 111
Navigation, p4
I One way to think about the difference between the two is in
terms of the relationship between the robot’s start point and
the goal point.
I If there is a clear line of sight between the start point and the
goal, then we only need to worry about obstacle avoidance.
I Just avoiding some debris that isn’t on the map
9 / 111
Navigation, p5
I However, if there is no line of sight from start to goal, then we
have to find a path.
I Typically path segments will be between two points between
which there is a line of sight.
I Path segments connect waypoints
10 / 111
Visibility graph
I Direct implementation of line-of-sight.
I Connect up all the vertices in the map.
I Given the line segments, look for the shortest path from start
to goal.
I Then translate the path into a series of waypoints (i.e., the
end points of the line segments).
11 / 111
Visibility graph, p2
I Given the visibility graph on the previous slide, there is an
obvious problem with using the lines as a guide for where the
robot should go.
I What is it?
I Routes at the moment run arbitrarily close to the vertices of
objects.
I Problems with collisions
I Fix this by expanding objects by enough that the robot will
still clear them.
I More than half the diameter of the robot.
12 / 111
Voronoi diagram
I A Voronoi diagram is a way to divide up a plane (a map).
I Given a set of points P , a Voronoi diagram is a set of polygons
such that the points inside each polygon are closer to one
member of P than any other.
13 / 111
Voronoi diagram, p2
I Can extend this to cases where P is a set of objects.
I Treat the line segments exactly like the edges in the visibility
graph.
14 / 111
Voronoi diagram, p3
I The lines are not necessarily lines of sight
I As above they may bend.
I However, they are object free, and so can be followed just like
lines of sight can.
15 / 111
Voronoi diagram, p4
I Voronoi diagrams also have a nice property in terms of
path-following.
I A robot that is maximising its distance from objects will follow
the lines in the Voronoi diagram.
I This means that we can again reduce the path to a set of
waypoints.
I Head to the next waypoint while maximising distance from
objects (obstacles).
16 / 111
Asides
I Voronoi diagrams work in 3D also.
17 / 111
Asides, p2
I Voronoi diagrams were also famously used by John Snow to
identify the source of the 1854 cholera epidemic in London.
18 / 111
Cell-based maps
I Previously we talked about a variety of different cell-based
maps…
19 / 111
Cell-based maps, p2
I Exact cell decomposition
20 / 111
Cell-based maps, p3
I Fixed cell decomposition
21 / 111
Cell-based maps, p4
I Adaptive cell decomposition
22 / 111
Cell-based maps, p5
I Given the maps, we still want to figure out a sequence of line
segments.
I Not quite so straightforward for cell-based maps.
I We will look at two general approaches to do path-finding:
I Explicit search of a connectivity graph
I Wavefront planning
I These are really the same thing in different guises…
23 / 111
Connectivity graph
I We need to identify which cells are next to which other cells.
24 / 111
Connectivity graph, p2
I The question is how to figure out a path from the graph.
I When the graph is complex, we need to use search techniques.
I This is also the case for the connectivity graphs we get
automatically from the visibility graph or Voronoi diagram
approaches.
I Standard approaches to search:
I Breath first
I Depth first
I A*
I Plus there are robotics-specific approaches like D*.
25 / 111
Search
I A general algorithm for search is:
agenda = initial node;
while agenda not empty do {
state <- node from agenda; new nodes = nodes connected to state; if goal in new nodes then { return solution; } add new nodes to agenda; } I Note that this doesn’t generate a set of waypoints, it just looks for the goal state. I In fact, it assumes that there are already set of possible waypoints. 26 / 111 Search, p2 I Let’s think about how this search would work on the connectivity graph: 27 / 111 Search, p3 I To use the algorithm we need to decide how to do the selection in this line: state <- node from agenda; and how to do the addition in this line: add new nodes to agenda; 28 / 111 Search, p4 Depth-first search: I Takes the first node on the agenda; I Adds new nodes to the front of the agenda. I Leads to a search that explores “vertically”. Breadth-first search: I Takes the first node on the agenda; I Adds new nodes to the back of the agenda. I Explores all the nodes at one “level” before looking at the next level. 29 / 111 Search, p5 I A* search focuses the search by giving each node a pair of weights: I How far it is from the start; and I How close it is to the goal. I The cost of the node is then the sum of the weights. I We pick from the agenda by choosing the node with the lowest cost. (Choosing like this means we don’t have to worry about what order we put nodes onto the agenda). 30 / 111 Search, p6 I In some domains we have to design clever functions to determine what “far” is. I In robotics we can just use Euclidean or Manhattan distance between points: I Euclidean distance des,g = √ (xg − xs)2 + (yg − ys)2 I Manhattan distance dms,g = |(xg − xs)|+ |(yg − ys)| I Of course the distance to the goal may be an underestimate (may be no route through), but it turns out that this is a good thing for A*. 31 / 111 Search, p7 I Often in robotics we need to replan. I D* is a version of A* that keeps track of the search that led to a plan and just fixes the bits that need to be fixed. I Quicker than replanning from scratch. I Usually have to replan from the robot to the goal and the only change is near the robot. I That is where the robot senses failure. 32 / 111 Search, p8 I In all these approaches we have to extract the waypoints after we find the goal. I First we identify the sequence of cells. I As we search we can build a plan for each node we visit. I The plan for each node is the route to its parent plus the step to the node. I When we get to the goal, we have the plan. I Then we build a waypoint from each grid cell. I Typically the centre of gravity of the cell. 33 / 111 Wavefront planning I Also known as Grassfire, wildfire or NF1. I Essentially breadth-first search in a convenient form for application to grid-based maps: 1. Start at the cell containing the goal and label it 0. 2. Take every unlabelled cell that is next to a cell labelled n and label it n + 1. 3. Repeat until the cell containing the start is labelled. I Then read the sequence of cells to traverse by following the labels down from the start, choosing the lowest numbered label at each step. I Works especially well with occupancy grids, where the obstacles are already factored into the map. 34 / 111 Wavefront planning, p2 I Here’s an example: 35 / 111 Bug algorithms I Bug algorithms assume localization but no map. Bug 1 Algorithm: I When you meet an obstacle you follow around the edge. I Leave the obstacle at the point closest to the goal. I Circle the obstacle to be sure that you know where this point is. 36 / 111 Bug algorithms, p2 37 / 111 Bug algorithms, p3 I The second bug algorithm improves on the performance of Bug 1. Bug 2 Algorithm: I Follow the obstacle always on the left or right side. I Leave the obstacle if you cross the direct (line of sight) connection between start and goal. 38 / 111 Bug algorithms, p4 39 / 111 Bug algorithms, p5 I Works even on very complex obstacles 40 / 111 Potential field I Robot is treated as a point under the influence of an artificial potential field. I The goal attracts it and obstacles repel it. I It’s like the goal has a “spring” that draws the robot towards it and away from obstacles that are in its path 41 / 111 Potential field, p2 I Generated robot movement is similar to a ball rolling down the hill I Lots of possibilities to get stuck in local minima. 42 / 111 Potential field, p3 I The idea is that potential energy is stored in the environment. I The robot wants to minimise its potential energy. I So it moves down the potential energy gradient. I Goals “attract” potential energy. I Obstacles “repel” potential energy. 43 / 111 Vector Field Histogram I Approach that uses sensor readings to tell the robot how to avoid obstacles. I Representing the area around the robot as a grid, compute the probability that any square has an obstacle. I Provides a local map to decide how the robot should move. 44 / 111 Vector field histogram, p2 I The local map is reduced to a 1 DOF histogram: I Then compute the steering angle for the best gap. I Best selected using function G which combines: G = a. target-direction + b. wheel-orientation + c . previous-direction 45 / 111 VFH+ I An issue with VFH is that it does not account for how the robot can really move. I The best gap could be one that the robot has to stop and do some complex maneuver to go through. 46 / 111 VFH+, p2 I VFH+ considers motion on trajectories. I Any turn that has a trajectory that intersects an obstacle is blocked 47 / 111 VFH+, p3 I VFH in action. 48 / 111 VFH+, p4 I VFH and VFH+ are limited if narrow areas (e.g., doors) have to be traversed. I Local minima might not be avoided. I Reaching the goal can not be guaranteed. I Dynamics of the robot not really considered. 49 / 111 Curvature velocity methods I Go further than VFH+ in modelling the motion of the robot. I Transform obstacles into the velocity space of the robot. I Apply acceleration constraints to determine possible velocities. 50 / 111 Outline Today Navigation Cognition Behaviour-Based Systems Multi-Robot Systems 51 / 111 Cognition I Environment I State I Memory I Knowledge Representation 52 / 111 Environment Robot environments are characterized by various properties: I accessible vs inaccessible I In an accessible environment, a robot has access to all the necessary information required to make an informed decision about its actions. I deterministic vs nondeterministic I In a deterministic environment, any action that a robot undertakes has only one possible outcome. I episodic vs non-episodic I In an episodic environment, activity proceeds as a series of repeated episodes. I static vs dynamic I In a static environment, things change only due to actions effected by the robot. I discrete vs continuous I In a discrete enviroment, sensor readings and actions have a distinct, separable values. 53 / 111 State I A robot’s state refers to knowledge about itself and its environment. I Kinematics is the study of the correspondence between actuator mechanisms and the resulting motion, which can be either: I linear; or I rotary. I Kinematics answers questions like: I Did I go as far as I think I went? (e.g., the result of linear motion) I Did I extend my arm as far as I think i did? (e.g., the result of rotary motion) I A robot’s environment is full of information. It is important to determine what is relevant to represent, given the robot’s abilities and task. I What properties can be sensed? I How can the sensed information be stored in a useable and useful way? 54 / 111 Memory Like with humans, a robot’s memory is divided into 2 categories according to duration: I Short Term Memory I Long Term Memory 55 / 111 Memory: Short Term Memory (STM) I STM is transitory. I It is used as a buffer to store only recent sensory data. I It stores data used by only one behaviour. I For example: I avoid-past: avoid recently visited places to encourage exploration of novel areas I wall-memory: store past sensor readings to increase correctness of wall detection 56 / 111 Memory: Long Term Memory (LTM) I LTM is persistent. I Metric maps use absolute measurements and coordinate systems. I Qualitative maps use landmarks and their relative relationships to each other. I For example: I Markov models are graph representations which can be augmented with probabilities for each action associated with each sensed state. 57 / 111 Components of Knowledge Representation I State — A robot’s state can (which comprises knowledge about the robot and its environment) can be totally observable, partially observable or unobservable. States can be discrete or continuous, making it easier or more difficult (respectively) to distinguish one state from another. I Spatial information — Spatial information is a description of the navigable surroundings in a robot’s environment and their structure. Spatial information is typically stored in a metric or topological map. I Objects — Objects are categories and/or instances of detectable things in the robot’s environment. 58 / 111 Components of Knowledge Representation, p2 I Actions — Actions that a robot can perform are part of its knowledge representation. This includes the expected outcomes of specific actions on the robot and on its environment. I Self/ego — A robot stores proprioception (sensing of its internal state), its own self-limitations and capabilities. These include information about perceptions (how to sense) and behaviours(how to act). I Intentional — A robot’s intentions are comprised of its goals, its plans to achieve those goals and its intended actions that make up the plans. 59 / 111 Types of representations I Maps I Euclidean map — Represents each point in space according to its metric distance to ll other points in the space I Topological map — Represents locations and their connections, i.e., how/if they can be reached from one another; but does not contain exact metrics I Cognitive map — Represents behaviours; can store both previous experience and use for action. Used by animals that forage and home (animal navigation). May be simple collections of vectors. 60 / 111 Types of representations, p2 I Graphs — I Represent the relationship between states (nodes in the graph) and actions (links between nodes). The links indicate how to move from one state to another, based on an action. I Can also represent other types of cause/effect or relational information other than state/action pairs. I Markov models — I Associate probabilities with states and actions. I In a graph, actions are given probabilities (usually determined experimentally, by observation) indicating how likely it is that an action taken in one state will lead to another state. It is thus possible to have a single action taken in one state to lead to multiple possible subsequent states, each with a different probability. 61 / 111 Outline Today Navigation Cognition Behaviour-Based Systems Multi-Robot Systems 62 / 111 Behaviour-Based Systems I Control models I Behaviour-based models I Expressing behaviours I Behaviour coordination I Emergent behaviour 63 / 111 Control models There is distinction between: I Classic model-based control I Focusses on symbolic representations I Based on “good old-fashioned AI” – e.g., [McCarthy, 1958] I Newer behaviour-based control I Focuses on numeric representations I Based on “nouvelle AI” – e.g., [Brooks, 1986] I There are also hybrid models that combine aspects of both model-based and behaviour-based. 64 / 111 Control models, p2 I Deliberative models: Sense, Plan, Act I Provide a functional decomposition I Systems consist of sequential modules achieving independent functions, such as: “Sense world”, “Generate plan” I Reactive models I Provide a task-oriented decomposition I Systems consist of concurrently executed modules achieving specific tasks, such as: “Avoid obstacle”, “Follow wall” 65 / 111 Control models, p3 I Two orthogonal control flows: motorsensor sensor/motor control world model planning sensor/motor control world model planning sensor motor vertical horizontal 66 / 111 Behaviour-based models I They are characterized by behavioural decomposition, rather than a functional or a task-oriented decomposition. I Systems consist of sequential modules achieving independent functions. I They provide a natural fit to robotic behaviour. I Behaviour-based models generate a motor response from a given perceptual stimulus. I The basis for these systems is in biological studies; and as a result, biology is an inspiration for the design of many behaviour-based models. I The field of Artificial Life or ALife focuses on the development of computational models of natural phenomena, including behaviour of individual and groups of animal(s). 67 / 111 Behaviour-based models, p2 I A behaviour is anything observable that the system/robot does. I How do we distinguish internal behaviours (components of a behaviour-based system) and externally observable behaviours? I Reactive robots display desired external behaviours. For example: “Avoiding”; “Collecting cans”; “Walking” I But a controller consists of a collection of rules, possibly organized in layers (e.g., subsumption architecture). I Behaviour-based models actually consist of and are programmed in behaviours, which have higher granularity than rules, extended in time (as opposed to rules, which are typically short-term), and capable of using and maintaining sophisticated knowledge representations. 68 / 111 Behaviours vs Actions I It is often hard to distinguish between a behaviour-based system and a classical, action-based system. I We make a comparison here. 69 / 111 Behaviours vs Actions, p2 A behaviour . . . I is based on dynamic processes I that operate in parallel, I that lack of central control, and I that provide fast couplings between sensors and motors. I exploits emergence I which are side-effects from combining processes, and I often use properties of the environment. I tends to be reactive. 70 / 111 Behaviours vs Actions, p3 An action . . . I is discrete in time, I with well defined start and end points, and I allows for pre- and post-conditions. I avoids side-effects I because it is a small, atomic description of one (or a few related) steps, and I because it also avoids conflicts. I tends to be deliberative. I Actions are building blocks for behaviours. 71 / 111 Distinguishing behaviour-based systems Characteristics: I Achieve specific tasks/goals (e.g., “Avoid Others”, “Find Friend”) I Typically execute concurrently I Can store state and be used to construct world models I Can directly connect sensors to effectors I Can take inputs from other behaviours and send outputs to other behaviours (e.g., can be connected in behaviour networks) I Typically higher-level than actions (e.g., a behaviour might be “Go Home”, whereas an action would be “Turn left 45 degrees”) I Typically closed loop, but extended in time 72 / 111 Distinguishing behaviour-based systems, p2 Key Properties: I Ability to act in real time I Ability to use representations to generate efficient behaviour I Ability to use a uniform structure and representation throughout 73 / 111 Distinguishing behaviour-based systems Challenges: I How can a representation be effectively distributed over the behaviour structure? The time scale must be similar to that of the real-time components of the system. The representation must use the same underlying behaviour structure for all system components. I Some components may be reactive. I Not every component is involved with representational computation. I Some systems use a simple representation. I As long as the basis is in behaviours and not rules, then the system is a behaviour-based system. 74 / 111 Expressing behaviours I Behaviours can be expressed using various representations. I When a control system is being designed, the task is broken down into desired external behaviours. I Behaviours can be expressed using a variety of models I Functional notation I FSA (Finite State Automata) diagrams I Subsumption Architecture I Stimulus Response (SR) formalism 75 / 111 Expressing behaviours, p2 I Strengths and weaknesses of various behavioural encodings: Strengths: I Support for parallelism I Run-time flexibility I Timeliness for development I Support for modularity Weaknesses: I Niche targetability I Hardware retargetability I Combination pitfalls (local minima, oscillations) 76 / 111 Functional notation I Mathematical model: I represented as triples (S ,R, β) S = stimulus R = range of response β = behavioural mapping between S and R I Easy to convert to functional languages like LISP I For example: coordinate-behaviours [ move-to-classroom ( detect-classroom-location ), avoid-objects ( detect-objects ), dodge-students ( detect-students ), stay-to-right-on-path ( detect-path ), defer-to-elders ( detect-elders ) ] = motor-response 77 / 111 FSA diagrams I Finite State Automata can be used to show sequences of behaviour transitions, where states represent behaviours. I Situated Automata are a formalism for specifying FSAs that are situated in a particular environment I Tasks are described in high-level logic expressions, as a set of goals and a set of operators that achieve (ach) and maintain (maint) the goals. I (ach in-classroom) I (maint avoid-objects) I Once defined, tasks can be compiled into circuits, which are reactive. 78 / 111 FSA diagrams, p2 I For example: (defgoalr (ach in-classroom) (if (not start-up) (maint (and (maint move-to-classroom) (maint avoid-objects) (maint dodge-students) (maint stay-to-right-on-path) (maint defer-to-elders))))) 79 / 111 Subsumption architecture I Subsumption Architecture [Brooks, 1986] Components: I Reactive elements I Behaviour-based elements I Layered approach based on levels of competence I Uses an augmented Finite State Machine (FSM) for each behaviour 80 / 111 Subsumption architecture, p2 I Each comoponent: reset suppressioninhibition behavior model FSM OUTPUTINPUT 81 / 111 Subsumption architecture, p3 I Combines FSMs in a sort of layered, circuit diagram: task layer emergency layer motion layer obstacles stuck? reverse collect turn forward S E N S O R S M O T O R S 82 / 111 Stimulus-Response formalism The Stimulus-Response formalism is based on the premise that a behavioural response in physical space has a strength and an orientation. I Expressed formally as (S ,R, β), where: I S = stimulus, necessary but not sufficient condition to evoke a response; internal state can also be used as a stimulus I R = response I β = behavioural mapping categories, which can be: null, or discrete, or continuous I Mapping can either be: I Discrete I Continuous 83 / 111 Stimulus-Response formalism, p2 Discrete Mapping I Expressed as a finite set of situation-response pairs/mappings I Mappings often include rule-based (IF-THEN) formulae. I Examples: I Subsumption language Continuous Mapping I Instead of discretizing the input and output, a continuous mathematical function describes the input-output mapping. I Can be simple, time-varying, harmonic. I Examples: I Potential fields I However, here are problems with local minima, maxima, oscillatory behaviour. 84 / 111 Behaviour coordination I Behaviour-based systems consist of collections of behaviours. I Execution must be coordinated in a consistent fashion. I Coordination amongst behaviours can be competitive, cooperative, or a combination of the two. 85 / 111 Behaviour coordination, p2 Competitive coordination: I Perform arbitration: selecting one behaviour among a set of candidates I priority-based: subsumption I state-based: discrete event systems I function-based: spreading of activation action selection 86 / 111 Behaviour coordination, p3 Cooperative coordination: I Perform command fusion: combining outputs of multiple behaviours I voting I fuzzy (formalized voting) I superposition (linear combinations): potential fields, motor schemas, dynamical systems 87 / 111 Behaviour coordination, p4 I The problem of deciding what to do next is considered either: I an Action-Selection Problem, or I a behaviour-Arbitration Problem. 88 / 111 Emergent behaviour I Emergence is an important but not well-understood phenomenon. It is often found in behaviour-based robotics. I Robot behaviours “emerge” from interactions between rules, behaviours, and/or with the environment. Coded behaviour is in the programming scheme. Observed behaviour is in the eyes of the observer—it emerges! There is no one-to-one mapping between the two! 89 / 111 Emergent behaviour, p2 I The notion of emergence depends on two aspects: I The existence of an external observer, to observe and describe the behaviour of the system I Access to the internals of the controller itself, to verify that the behaviour is not explicitly specified anywhere in the system 90 / 111 Emergent behaviour, p3 I Unexpected vs Emergent I Some researchers say the above is not enough for behaviour to be emergent, because above is programmed into the system and the “emergence” is a matter of semantics. I So emergence must imply something unexpected, something “surreptitiously discovered” by observing the system. But “unexpected” is highly subjective; it depends on what the observer was expecting. Naïve observers are often surprised. Informed observers are rarely surprised. I Once a behaviour is observed, it is no longer unexpected. Is new behaviour then “predictable”? 91 / 111 Example: Wall Following Wall following behaviour can be implemented with these rules: I if too far, move closer I if too close, move away I otherwise, keep on going I Over time, in an environment with walls, this will result in wall-following. 92 / 111 Example: Wall Following, p2 forward motion, obstacle avoidance coded behavior with slight right turn observed behavior wall following 93 / 111 Example: Wall Following, p3 I Is this emergent behaviour? I It is argued yes because: I The robot itself is not aware of a wall, it only reacts to distance readings. I The concepts of “wall” and “following” are not stored in the robot’s controller. I The system is just a collection of simple rules. 94 / 111 Outline Today Navigation Cognition Behaviour-Based Systems Multi-Robot Systems 95 / 111 Multi-Robot Systems I Techniques I Surveillance Applications I Localisation I Planning I Coordination 96 / 111 Multi-Robot Systems: Techniques I Techniques include: I Learning of controllers for teams of robots I Swarm-based robotics, which use large numbers of small robots and employ biologically inspired techniques 97 / 111 Multi-Robot Systems: Techniques, p2 I Techniques have been developed to ensure that I the entire boundary of a space is visited I search finds a specific target I a human-robot team can exchange search roles flexibly and appropriately 98 / 111 Multi-Robot Systems: Techniques, p3 I Foraging: robots systematically sweep an area, search for and gather objects of interest I Exploration: robots investigate an area and build a shared “map” of the area/resources/features 99 / 111 Multi-Robot Systems: Surveillance Applications I Surveillance: robots observe an area for changes over time I Formation approaches: I applying control theory I stabilizing formations of multiple agents I moving in formation where the environment is not conducive to maintaining formation 100 / 111 Multi-Robot Systems: Surveillance Applications, p2 I Strategies: I Formation: structuring relative positions of multiple robots I Caging or Object Closure: I instead of single-robot idea of caging, where a multi-fingered hand surrounds an object, multi-robot caging implies a group of robot surrounding or constraining an object restricting an object to a specific set of configurations using multiple robots; uses local information with minimal communication and sensing and is based around vector fields I comparing experimental data gathered on real robots with only (omnidirectional) cameras to ground truth supplied by an overhead camera I Coverage: I surveilling pursuer, while continuing to keep an eye on an evader examining every point on the boundary of a 2D space I swarm-based approaches 101 / 111 Multi-Robot Systems: Surveillance Applications, p3 I Challenges: I Maintaining communication (wifi/radio connectivity) during exploration I Information fusion fusing data from multiple robots to give position estimates of objects of interest I finding an object with multiple robots I cooperative robot-human searching of an environment in which there is an “adversarial target” that must be cleared I Task/region allocation I deciding how to search a space with a group of searchers that will find an evading target to result in “guaranteed search” I analyzing range of auction bidding rules for auctions in which robots bid for targets; robots have to visit all targets that they “win”, and the team is judged by combinations of the distances travelled by all robots visiting their targets (e.g., traveling salesman problem) I implementing foraging using robot swarms 102 / 111 Multi-Robot Systems: Cooperative Localization I Multiple robots jointly estimate each other’s positions I A group of robots can localize faster (than they can on their own) if they share information. I Approaches: I adding a detection model to the usual particle-filter, sensor model and motion model; when one robot is spotted by another, it updates its location with information that takes into account the belief the other robot has on its position I showing that it is possible to use wireless ethernet—in particular the strength of wireless ethernet signals—as the basis for localization I planning the trajectories of multiple robots in order to improve their localization performance 103 / 111 Multi-Robot Systems: Multi-robot SLAM I Multi-robot Simultaneous Localization And Mapping (SLAM) I additional information from several robots can speed up single-robot SLAM I though multiple robots can also complicate the situation I Approaches: I developing vision-based multi-robot SLAM I applying particle filters to multi-robot SLAM I providing a strategy for accurate control of a group of robots (i.e., keeping on the desired path while localizing and mapping) I considering performance bounds 104 / 111 Multi-Robot Systems: Planning I Aspects of planning in multi-robot systems: I path and motion planning I task planning I Challenges in multi-robot planning: I dynamic environments, robots with multiple goals I motion planning for multiple robots I maintaining radio/wifi communication layered on top of multi-robot route-planning I task planning for multi-robot systems under time constraints I Strategies for multi-robot path planning: I multi-robot path planning using probabilistic roadmaps I planning in terms of roles, allowing robots to change roles through “exchange” as situations arise I shared memory task scheduling for a heterogenous multi-robot team making use of a “shared global unit” to reduce communication overhead 105 / 111 Multi-Robot Systems: Coordination Multi-robot Coordination I Standard tasks: I Traffic control I Box-pushing I Foraging I Approaches: I Merging the plans of multiple robots; this type of coordination is an intersection of several robots’ plans—they aren’t working together, but they are in the same space at the same time I Using parallel stochastic hill-climbing for coordinating a small team of robots in a pursuer-evader task I Dynamically coordinating robots using task assignment and integrates data on obstacles I Coordinating movement of objects by homogeneous teams of robots 106 / 111 Multi-Robot Systems: Task Allocation Task Allocation: dividing responsibilities in a group of individuals I Hard problem because: I robot team requirements change over time I abilities of individual robots are conditioned on changing locations I different robots have different capabilities 107 / 111 Multi-Robot Systems: Task Allocation, p2 I Approaches: I providing a local approach to task allocation in a multi-robot team; robots only use information from immediate neighbors I performing concurrent mapping and localization and showing improvements with multi-robot data collection I formalizing multi-robot task allocation and analyzes the computational and communication requirements of some approaches I performing dynamic task allocation when the coordination is distributed I learning using Alliance which aims to handle heterogeneous teams of robots in a variety of scenarios I learning specialities of robots using reinforcement learning and using a blackboard to distribute knowledge sharing I Contrasting task allocation in robot swarms using random assignment with more measured approaches that use different amounts of bandwidth and time to run 108 / 111 Multi-Robot Systems: Market-based Approaches Many apply market-based approaches to multi-robot coordination and task allocation, such as auctions I Example: organizing robots for exploration tasks I Areas to explore are offered “for sale”; robots bid based on distance to locations on offer; allocation favors lower bids; tends to allocate areas closer to robots; market constructed to ensure that robots are not idle when several robots are close to the same unexplored area. I tasks are offered “for sale” to robot team members I robots indicate how much they are willing to “pay” for tasks I tasks are allocated based on bids for them 109 / 111 Multi-Robot Systems: Market-based Approaches, p2 I Approaches: I Murdoch, auction-based method for coordination I Hoplites, uses market-based techniques to provide tight coordination of multi-robot teams I using auction-based coordination mechanisms to orchestrate movement of robots to certain points within time windows I focusing on bid evaluation in market-based task allocation mechanism 110 / 111 References I Some content from: Introduction to Autonomous Mobile Robots, by Roland Siegwart, Illah R. Nourbakhsh and Davide Scaramuzza (2011), MIT Press. Robotic Motion Planning, by Howie Choset, http://www.cs.cmu.edu/~motionplanning/ I Many slides thanks to Prof Simon Parsons. 111 / 111 http://www.cs.cmu.edu/~motionplanning/ Today Navigation Cognition Behaviour-Based Systems Multi-Robot Systems