BATALIN FEB 13 04

Information about BATALIN FEB 13 04

Published on January 7, 2008

Author: Esteban

Source: authorstream.com

Content

Symbiosis: Cooperative Algorithms for Mobile Robots and a Sensor Network:  Symbiosis: Cooperative Algorithms for Mobile Robots and a Sensor Network by Maxim Batalin Supervisor (USC): Gaurav Sukhatme T2 ? ? “Sym·bi·o·sis - the intimate living together of two dissimilar organisms in a mutually beneficial relationship” :  “Sym·bi·o·sis - the intimate living together of two dissimilar organisms in a mutually beneficial relationship” -Merriam-Webster Online Dictionary - http://www.webster.com Contents:  Contents Introduction Problems and solutions with Mobile Robots (MR) and Sensor Networks (SN) Coverage and Exploration through Sensor Network Deployment; Sensor Network Repair and Maintenance – Implicit; Probabilistic Navigation; Task Allocation Problem (scheduling); DINTA; DINTA-MF; Sensor Network Repair and Maintenance - Explicit; Current Work: Task Allocation for NIMS; Summary Introduction:  Introduction Why use both Mobile Robots and Sensor Networks?:  Why use both Mobile Robots and Sensor Networks? Sensor Network provides distributed: Sensing; Computation; Communication; Ubiquitous computing is an active area of research and investment, hence can utilize intelligence which will be present in an environment in the future At the same time Mobile robots deploy, repair and maintain the network, while accomplishing tasks that require mobility; Robots can be simpler, cheaper and don’t need as many; Can solve wider variety of problems Overall objectives:  Overall objectives We are motivated by the idea that MRs and SN each could leverage strengths from the other Goal: Build a collaborative ‘symbiotic’ system in which mobile robots and a sensor network solve tasks cooperatively and coexist benefiting each other Assumptions: Global information is not accessible (no GPS, no map, etc.) Neither robot localization nor mapping is performed – hence robots can be simple Environment can be dynamically changing Assume that a collection of nodes “large enough” Do not consider power constraints Validation Platform:  Validation Platform Pioneer 2DX Laser (for obstacle avoidance) Compass Wireless ethernet PC-104 stack (Pentium 1Ghz) Motes Atmel ATmega 128L Program Flash Memory 128K bytes Measurement (Serial) Flash 512K bytes Configuration EEPROM 4 K bytes Serial Communications UART 916 MHz Multi-Channel Radio Transceiver Player/Stage engine Problems and solutions with Mobile Robots and Sensor Networks:  Problems and solutions with Mobile Robots and Sensor Networks Coverage and Exploration:  Coverage and Exploration Deploy a group of robots maximizing sensor coverage; Cover/Explore every point of environment with an onboard sensor; Can’t tell if coverage is complete; Can’t recover robots; Require a LOT of ‘expensive’ robots; Use Sensor Network; Approach:  Approach M. Batalin, G. S. Sukhatme, Coverage, Exploration and Deployment by a Mobile Robot and Communication Network, Telecommunications Systems, April 2004 (accepted, to appear) M. Batalin, G. S. Sukhatme, Efficient Exploration Without Localization Proceedings of the 2003 IEEE International Conference on Robotics and Automation (ICRA'03), Taipei, Taiwan, May 12 - 17, 2003. Robot Loop If no beacon within radio range deploy beacon Else move in direction suggested by nearest beacon Beacon Loop Emit least recently visited direction Simulation Experiment:  Simulation Experiment Sensor Network Repair and Maintenance - Implicit:  Sensor Network Repair and Maintenance - Implicit Graph Model:  Graph Model Consider G = (V, E) - regular square lattice; Coverage - the time it takes the robot to visit every node of the graph; No information– Random Walk (RW) RW(G)= ω(VlogV ) and RW(G)= o(V2) Full information – DFS DFS(G) = Θ(V + E) < 4V Proposed algorithms data is taken on graphs of 25, 49 and 100 nodes Every node was tried as starting point; 50 experiments per starting point; Experimental Results analysis:  Experimental Results analysis Conjecture 1: The asymptotic cover time of our algorithm is less than o (V log V); While proposed algorithm designed for coverage also can be applied for mapping; The graph mapping time (MT) is: MT < d * maxi(CTi) (i.e. o (V log V)) d is the maximum degree of G (4 in case of square lattice); CTi is the i-th cover time (o(VlogV)); Conjecture 2: Our algorithm produces a map of the environment in asymptotic time faster than o (V log V); Simulation Experiments:  Simulation Experiments Direct correspondence between the graph model and simulations; Support our conjecture that the cover time is less than o(nlogn); Benefits:  Benefits A static sensor network is deployed: can be used for numerous network applications; guarantees that every point of environment would be eventually covered by the mobile robots; etc. Robots can: be used for exploration, patrolling and coverage tasks; restore the static sensor network in case of damage; retrieve robots; system knows when full coverage is achieved; Summary:  Summary Theoretical analysis shows that trade offs in the assumptions affect the outcome significantly: RW – robot does not have or assume anything: RW(G)= ω(VlogV ); Proposed Approach – the number of nodes is ‘enough’: ω(V ) and o(VlogV) DFS – nodes of three colors, perfect localization and navigation: DFS(G) = Θ(V + E) < 4V Proposed algorithm outperforms other algorithms if localization and perfect navigation cannot be assumed; Probabilistic Navigation:  Probabilistic Navigation Introduction:  Introduction How to navigate from point A to point B; A fundamental problem in robotics; No a priori information about the environment; Use Sensor Network; Transition Probabilities:  Transition Probabilities While robot deploys and traverses sensor network from node to node it can determine transition probabilities: Robot stores determined probabilities on appropriate nodes; Navigation Field computation:  Navigation Field computation Suppose transition probabilities are determined for all nodes; If a goal node is specified, the information is propagated through the network and the ‘navigation field’ is computed using: Where - V is the utility value, C(s, a) is the cost associated with an action, P(s’|s, a) is the transition probability of arriving to node s’ if an action a was taken at node s, π(s) is the policy, or direction that the node s is going to suggest for the robot in the vicinity. Distributed Computation:  Distributed Computation Suppose the SN is flooded with goal node data; Every node updates own utilities according to utility equation; After the utilities are computed, every node computes an optimal policy for itself according to policy equation; Note that the action policy computation is done only once, and does not need to be recomputed, unless the goal changes; Note that if neighbors of all nodes are known exactly the system converges after a single iteration. Basic algorithm:  Basic algorithm Assume that SN deployed and Navigation Field is computed; Closest Node suggests direction of motion; Robot moves straight in a suggested direction; Determine if close to the next node based on signal strength: If no, repeat 2; If yes, start 1; M. Batalin, G. S. Sukhatme, Coverage, Exploration and Deployment by a Mobile Robot and Communication Network, Telecommunications Systems, April 2004 (accepted, to appear) Simulation Experiment:  Simulation Experiment Node-to-node navigation: Move in suggested direction, switch to closest node, repeat; Probabilistic Navigation in Real Environment:  Probabilistic Navigation in Real Environment My Cube Real-World Navigation Challenges:  Real-World Navigation Challenges Cubicle environment is ‘narrow’, hence precision is required; Compass or IMU proved to be useless inside; Implementation should be simple enough for simple robot; Algorithm should be based purely on signal strength: Different antennas, not truly omnidirectional; Ambient noise in the environment not constant with time; Hence raw signal strength thresholding or an observation model would not work reliably; Basic algorithm:  Basic algorithm Assume that SN deployed and Navigation Field is computed; Robot knows its initial heading and closest node; Closest Node suggests direction of motion; Robot moves in a suggested direction: Vector Field Histogram (VFH) algorithm is used for local navigation and obstacle avoidance Drives the robot from A to B avoiding obstacles on the path on the local scale (<= 2-3 meters); Author: J. Borenstein, available in Player/Stage; Determine if close to the next node (next slide): If no, repeat 2; If yes, start 1; M. Batalin, G. S. Sukhatme,M. Hattig, "Mobile Robot Navigation using a Sensor Network,“ To appear IEEE International Conference on Robotics and Automation, 2004 When to switch between the nodes?:  When to switch between the nodes? Similar to general state estimation problem; Difficult problem in general; Proposed algorithm which estimates when the robot is close to a node: Compute initial maximum average of the first i samples Compute a running average which is an average of j consecutive samples where j << i Threshold on ratio of averages Experiments – The Environment:  Experiments – The Environment 1 2 3 4 5 6 7 8 9 My Cube Experiments – Run 1:  Experiments – Run 1 1 9 Summary:  Summary Algorithm allows the robot to navigate precisely and reliably using a deployed sensor network. Approach differs from systems described in the literature by assuming that the map, localization, GPS, IMU and compass are not available; The navigation occurs through node-wise motion from node to node on the path from starting node to the goal node; We conducted 50 experiments for 5 different goals, totaling in over 1 km of traveled distance; In each of the 50 cases the robot successfully navigated to the goal node; Note that we considered an experiment to be successful if the robot approached the goal node to within 3m; Task Allocation Problem:  Task Allocation Problem Introduction:  Introduction Task Allocation (TA) is the problem of assigning resources (robots for example) to tasks; Offline TA is the problem of assigning resources to different tasks (processes) if the tasks‘ arrival distribution is known a priori; Task assignments are computed offline; Resembles Traveling Salesperson Problem, it is NP-Complete; Online TA is the problem of assigning resources to tasks if the distribution of the tasks’ arrival is NOT known a priori; The task assignment occurs in decision epochs. A decision epoch is a period of time during which only arrived tasks are considered for assignment. It is shown in literature that in case of Online TA the optimal solution assigns the tasks in a greedy fashion We consider an Online TA; Note that many real life TA problems are Online; Experimental Scenario:  Experimental Scenario We study a particular experimental scenario - emergency handling; Alarms are detected by nodes in the static network; The problem is to assign and navigate robots to different alarms; The goal is to minimize the cumulative alarm OnTime across all alarms, over the duration of the entire experiment; Alarm’s OnTime is a difference between the time the alarm was turned off by a robot and the time the alarm was detected by one of the nodes of the network; Distributed In-Network Task Allocation (implicit):  Distributed In-Network Task Allocation (implicit) Suppose sensor network monitors the environment; If an event is detected by node n it sends out a packet (n_id, weight, hop_count) Compute Navigation Field; This computation results in a direction which maximizes the net utility of the robot; If there are several events detected at the same time, a node computes direction towards the goal node with largest: Multi Field Distributed In-Network Task Allocation (explicit):  Multi Field Distributed In-Network Task Allocation (explicit) If an event is detected by node n it sends out a packet (n_id, time_of_event, weight, hop_count) Every node considers task assignment in decision epochs; At the end of current decision epoch, network synchronizes current positions of available robots; Since every node receives the same data – the node states are ‘in synch’ – an optimal greedy assignment is possible. Hence, every node maintains a suggested direction per task; Experimental results:  Experimental results Player/Stage simulations; Sensor Network of 25 motes; Groups of 1-4 robots, 10 trials/group 10 Alarms are drawn from the Poisson distribution with λ=1/60; Empty environment, A = 576 m2 Sensor Network Repair and Maintenance - Explicit:  Sensor Network Repair and Maintenance - Explicit Benefits of DINTA & DINTA-MF compared to other techniques:  Benefits of DINTA & DINTA-MF compared to other techniques Sensing, computation and communication are distributed; Provides sensor that is everywhere at the same time; Can estimate utilities directly; Does not rely on global information (no map, GPS, localization, etc.); Can be combined with other techniques to increase range of applications; M. Batalin, G. S. Sukhatme, “Using a Sensor Network for Distributed Multi-Robot Task Allocation,“ To appearIEEE International Conference on Robotics and Automation, 2004 M. Batalin, G. S. Sukhatme, "Sensor Network-based Multi-Robot Task Allocation," In IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1939-1944, 2003 Current Work: Task Allocation for NIMS :  Current Work: Task Allocation for NIMS Slide41:  84 91 NIMS Node Vertical Node (Ta, RH, PAR) Solar Cell Battery Pack Power Distribution Cable Imager With Pan/Tilt Actuator 47 m 50 m Problem Definition:  Assume a NIMS system (s1, s2, s3, …) and a Sensor Network deployed in the same area; Suppose nodes of the sensor network detect phenomena (p1, p2, p3, …) that require further study by a NIMS system; Compute an optimal assignment of : (s1, s2, s3, …) (p1, p2, p3, …) The problem is an instance of an Online Task Allocation problem Problem Definition Current Status:  Current Status Implemented a version of the algorithm in simulation; Porting to the lab NIMS system – a model of an actual node; In march plan experiments in James Reserve; Summary:  Summary Coverage and Exploration through Sensor Network Deployment; Sensor Network Repair and Maintenance – Implicit and Explicit; Probabilistic Navigation; Task Allocation Problem (scheduling); DINTA; DINTA-MF; Current Work: Task Allocation for NIMS; Symbiotic systems are beneficial and important to study Contacts:  Contacts Maxim A. Batalin Robotic Embedded Systems Laboratory Center for Robotics and Embedded Systems Computer Science Department University of Southern California Los Angeles, CA 90089, USA [email protected] http://www-robotics.usc.edu/~maxim

Related presentations


Other presentations created by Esteban

Chapter 15 Knee Conditions
28. 11. 2007
0 views

Chapter 15 Knee Conditions

S WATER
09. 10. 2007
0 views

S WATER

ELearning Conf collins
12. 12. 2007
0 views

ELearning Conf collins

Istvan Bilik
29. 10. 2007
0 views

Istvan Bilik

The Rise of Mussolini in Italy
01. 11. 2007
0 views

The Rise of Mussolini in Italy

intro cicero
01. 11. 2007
0 views

intro cicero

titanic
05. 11. 2007
0 views

titanic

00 18 pp7
05. 11. 2007
0 views

00 18 pp7

defence ficci
05. 11. 2007
0 views

defence ficci

bisnovatiykogan
13. 11. 2007
0 views

bisnovatiykogan

firm
22. 11. 2007
0 views

firm

UDSL Pres 4
26. 11. 2007
0 views

UDSL Pres 4

Insomnia
29. 11. 2007
0 views

Insomnia

ag environment
28. 12. 2007
0 views

ag environment

SAS781 016ArticleSlideShow
01. 01. 2008
0 views

SAS781 016ArticleSlideShow

Friendship Quotes
02. 01. 2008
0 views

Friendship Quotes

Lesson 16 Leader of Russia
26. 10. 2007
0 views

Lesson 16 Leader of Russia

Electronics 1 20 06
07. 11. 2007
0 views

Electronics 1 20 06

Slides4c
07. 01. 2008
0 views

Slides4c

NRES322 14
08. 01. 2008
0 views

NRES322 14

Weese MRSA
19. 11. 2007
0 views

Weese MRSA

Shore Stephen
13. 12. 2007
0 views

Shore Stephen

Gerberding 07 AAIDD
24. 10. 2007
0 views

Gerberding 07 AAIDD

halloween history
05. 11. 2007
0 views

halloween history

june25 natural dhananjay
20. 02. 2008
0 views

june25 natural dhananjay

BEST03
24. 02. 2008
0 views

BEST03

ch9
27. 02. 2008
0 views

ch9

TrainingPanel
29. 02. 2008
0 views

TrainingPanel

080407
14. 03. 2008
0 views

080407

cares
27. 03. 2008
0 views

cares

UNIDO1
30. 03. 2008
0 views

UNIDO1

Praes WR Glaser DGfPs
16. 11. 2007
0 views

Praes WR Glaser DGfPs

Tireoidites CM 2006
28. 12. 2007
0 views

Tireoidites CM 2006

sommaruga
25. 10. 2007
0 views

sommaruga

Card Sort Indian Artifacts
19. 11. 2007
0 views

Card Sort Indian Artifacts

Exodus08
24. 10. 2007
0 views

Exodus08

Arthur Sadoff
28. 09. 2007
0 views

Arthur Sadoff

research industry partnerships
16. 11. 2007
0 views

research industry partnerships

Molvir Flavi Toga 01 19 06
24. 10. 2007
0 views

Molvir Flavi Toga 01 19 06

Chris Aalberts
25. 12. 2007
0 views

Chris Aalberts

mission mech garden intro
11. 12. 2007
0 views

mission mech garden intro

library agent
30. 10. 2007
0 views

library agent

FallOffDutySafety
06. 11. 2007
0 views

FallOffDutySafety

cours sts intro gen 2005
12. 11. 2007
0 views

cours sts intro gen 2005

JanConrad mar10 06
14. 11. 2007
0 views

JanConrad mar10 06

re nsdi06 slides
18. 12. 2007
0 views

re nsdi06 slides

AMC Italy Intro CMonticelli
31. 10. 2007
0 views

AMC Italy Intro CMonticelli

CROSSMARC Rome Intro
31. 10. 2007
0 views

CROSSMARC Rome Intro

Liz presentation
28. 12. 2007
0 views

Liz presentation

anheuser1
05. 11. 2007
0 views

anheuser1

AUST Overview for Website
06. 11. 2007
0 views

AUST Overview for Website

2b lanciotti
24. 10. 2007
0 views

2b lanciotti

OWK2006 Dixon SBDC
29. 10. 2007
0 views

OWK2006 Dixon SBDC

L23 ch14
03. 10. 2007
0 views

L23 ch14

JAA etno maj 2005
01. 12. 2007
0 views

JAA etno maj 2005

Japansk encefalitt
24. 10. 2007
0 views

Japansk encefalitt

MM5 yhe
04. 01. 2008
0 views

MM5 yhe