BATALIN FEB 13 04

50 %
50 %
Information about BATALIN FEB 13 04
Education

Published on January 7, 2008

Author: Esteban

Source: authorstream.com

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 maxim@robotics.usc.edu http://www-robotics.usc.edu/~maxim

Add a comment

Related presentations

Related pages

feb - YouTube

YouTube Red Watch ... Actualidad FEB Play all. 2:24. Play ... Play now; #LEBPlata: Una noche para la historia en el Sáenz-Horeca Araberri (13·05·2016 ...
Read more

Mario Batali - Wikipedia, the free encyclopedia

Mario Batali Holiday Food : Family Recipes for the Most Festive Time of the Year (2000), ISBN 0-609-60774-X; Vino Italiano: The Regional Wines of Italy ...
Read more

Schalke 04 - Schalke04.de - Offizielle Website des FC ...

So., 13.09. 17:30: FC Schalke 04-1. FSV Mainz 05: 2:1 (1:1) ... FC Schalke 04: 1:4 ...
Read more

The Chew Episode Guide | Full Episode List - ABC.com

The Chew full episode guide offers a synopsis for every episode in case you a missed a show. ... 04 05/19/16 PG. ... 35:46 05/13/16 PG.
Read more

Die TOP100 Single Charts vom 13.05.2016

13.05.2016: down ..... down--> Neueinsteiger vom 13.05.2016-- ... 15.04.2016: Drake Feat. Wizkid & Kyla - One Dance: 3 Hoechste Platzierung: 1: 2: 19.02.2016:
Read more

Startseite - Deutsche Messe

04.06. - 05.06. MCM Hannover Comic Con Hannover 09.06. - 11.06. FOOD hospitality WORLD Bangalore Bangalore ... 13.10. - 15.10. CeBIT Bilisim Eurasia
Read more

biathlon-online.de - Das Biathlon Portal in Deutschland

Allgemein, Biathlon-News 13.04.2016. Ricco Groß mit Rückendeckung Richtung Olympia 2018. Die Verantwortlichen in Russland setzen auf Ricco Groß.
Read more

Mario Batali Recipes | The Chew - ABC.com

Get to know Mario Batali from The Chew. Read the official ABC bio, show quotes and learn about the role at ABC TV.
Read more

Mario Batali

Mario Batali Foundation Swing Session 2016. The Chef. Mario Batali. This form needs Javascript to display, which your browser doesn't support. Sign up here ...
Read more

Mario Batali - HarperCollins Publishers: World Leading ...

Mario Batali is the James Beard Award-winning author of eight cookbooks, including Molto Batali, Molto Gusto, Molto Italiano, and Spain ...
Read more