# kostas compass3 30

Information about kostas compass3 30

Published on January 7, 2008

Author: fazil

Source: authorstream.com

Slide1:  Robotics and Sensor Networks: Coverage, Localization and Mobility Kostas Bekris March 29, 2005 COMPASS project meeting Slide2:  What is the relation? Robotics and Sensor Networks are typically considered two unrelated fields. But: Robots can provide mobility to Sensor Networks. Sensor Networks can provide rich sensing information to Robots. and most importantly The two fields are facing many similar challenges. Slide3:  Robots for Sensor Networks Mobile nodes can be used to: Re-deploy and calibrate sensors, React to sensor failures and Deliver power. [Corke, Hrabar, Peterson, Rus, Saripalli, Sukhatme, 2004] Slide4:  Sensor Networks for Robots A network offers detailed sensing information to a robot that is not possible to acquire otherwise. Distributed computation over the network. Robots can form mobile sensor networks. [Batalin, Sukhatme, Hattig, 2004] Slide5:  Similar challenges Many of the problems are the same: Decision inference based on multiple sensing inputs Sensor fusion Location awareness Coordination Task allocation Workspace or sensor field coverage Compression of data Uncertainty Mobility Slide6:  Topics to cover I. Coverage Art-Gallery Problems (Computational Geometry) II. Localization Distributed Markov and Monte Carlo (Machine Learning) III. Mobility Artificial Potential Functions & Formation Control (Control Theory) Slide7:  I. Coverage Slide8:  Coverage in Sensor Networks Very important for deployment: Under-deployment might result in communication failures or failures in the sensing task Over-deployment can significantly increase the cost Typical Measure in Sensor Networks: Path Exposure [Meguerdichian, Koushanfar, Potkonjiak, Srivastava 2001] Slide9:  Art-Gallery Problem The original art gallery problem: Find the smallest number of point guards g(n) necessary to cover any polygon of n vertices. According to the art gallery theorem the necessary number is: g(n) = n/3 Finding minimum set of guards: NP-hard [Conversation between Klee and Chvatal 1972] [Chvatal 1975] [Aggarwal 1984] Slide10:  Heuristic Solution Greedy approach for map building in robotics: Place the first guard at the point of maximum visibility Next guard is placed where it sees the maximum area not visible to the first and so on The sub-problem of finding the next guard of maximum visibility is called: the Next-Best-View problem Slide11:  Various approaches Randomized algorithms compute the optimal location up to a constant factor approximation. Sampling-based techniques can be used for the most realistic case of sensors with limited-range. Decomposition methods compute cells that can be observed by limited range guards. [Cheong, Efrat, Har-Peled 2004] [Kazazakis, Argyros 2002] [Gonzalez-Banos, Latombe 2002] Slide12:  Robotic SN Deployment [Howard, Mataric, Sukhatme 2002] Incremental approach: select a node at a time to be deployed in a new location, a second nodes replaces it Build a centralized representation while maximizing network coverage and retaining line-of-sight communication. Slide13:  II. Localization Slide14:  Data for SN self-localization Received Signal Strength: for known transmission power, the propagation loss is measured to estimate the distance based on a propagation model. Time-of-arrival or time-difference-of-arrival: The propagation time can be directly translated into distance based on signal propagation speed. Angle-of-arrival: Systems estimate the angle at which signals are received. Slide15:  Localization Approaches [Bergamo, Mazzini 2002] Assume a subset of the nodes can self-localize (e.g. GPS) localize the rest relative to the beacons. Trilateration Triangulation MLE [Niculescu, Nath 2003] [Nasipuri, Li 2002] [Savvides, Han, Srivastava 2002] Slide16:  Uncertainty in Robotics [Fox, Burgard, Kruppa, Thrun: A probabilistic approach to collaborative multi-robot localization, 2000] Robots, like nodes of sensor networks, have to be aware of their location. Typical sensors in robotics: sonar, laser, cameras. Problem: inherent uncertainty in sensor measurements Probabilistic/bayesian techniques proven successful in dealing with uncertainty and providing robustness. Slide17:  Markov Localization Each robot maintains a belief for its position at time t Belt(L) where L is the robot’s configuration (e.g. {x,y,}). Initially, Bel0(L) follows a uniform distribution. Each robot collects data dt: Odometry: at Sensing observations: ot Detections of other robots: rt Slide18:  Updating the distribution The belief represents the posterior up to time t: Belt(L) = Pr(Lt|dt) Perception model: Pr(ot|L) Motion Model: Pr(L|at,L’) Updates after: Sensing: Belt(L) =   Pr(ot|L)  Belt-1(L) Action: Belt(L) = Pr(L|at,L’)  Belt-1(L’)  dL’ Slide19:  Multi-Robot Case Independence assumption: Pr(L1, …, Ln|dt) = Pr(L1|dt)  …  Pr(Ln|dt) Detections used to add additional constraints. Assume robot m detects robot n: Beltn(L) = Belt-1n(L)  Pr(Ln=L|rtm,Lm=L’)  Belt-1m(L’)  dL’ Slide20:  Monte-Carlo Localization Representation issue with the storage of distributions Monte Carlo approach: A distribution is a set of K weighted “particles”: S = { (Li,pi) | i=(1,…,K) } where: Li is a candidate position and pi is a discrete probability pi=1 Sensing leads to re-weighting the set of samples so as to agree with the measurements. Slide21:  An equivalent approach is to distribute the computation of a centralized Kalman filter to separate Kalman filters. More difficult problem: SLAM (Simultaneous Localization and Mapping) Incrementally generate a maximum likelihood map Probabilistically estimate the robots’ position More on Localization [Roumeliotis, Bekey 2002] Slide22:  Providing location aware services in buildings that are equipped with wireless infrastructure Build radio signal strength maps with multiple robots: For a pair of locations return the expected signal strength Sample the environment and build the map for the samples Localization for RSN [Hsieh, Kumar, Taylor 2004] [Ladd, Bekris, Rudys, Marceau, Kavraki, Wallach 2002] [Haeberlen, Flannery, Ladd, Rudys, Wallach, Kavraki 2004] Slide23:  III. Mobility Slide24:  Why mobility? Synoptic sensing implies either over-deployment (impractical – you cannot have sensor everywhere) or mobility Mobility allows the system to focus sensing where it is needed, when it is needed The initial deployment of static nodes cannot deal with all possible changes in the environment Slide25:  Energy Considerations [Dantu, Rahimi, Shah, Babel, Dhariwal, Sukhatme 2004] Example Mobile Platform: Robomote Slide26:  Goal of navigation approaches Navigational strategies for SN should not have extensive sensing and computational requirements. They should take advantage of the distributed nature of such networks. Computationally or memory expensive approaches are also not appropriate. Slide27:  Navigation Functions Many distributed navigation approaches are based on “navigation functions”. Construct a real-valued map: V: Cf  R with unique minimum at the goal and is maximal over Cf boundary. [Rimon, Koditschek 1992] Slide28:  Navigation Functions Then the robot at position p can move according to: where d is an arbitrary dissipative vector-field. Under additional requirements NFs guide the robot to the goal without hitting local minima. In the multi-robot case, each robot can act as an obstacle in the potential function of other robots. (p,p’) = -V(p) + d(p,p’) [Dimarogonas, Zavlanos, Loizou, Kyriakopoulos 2003] Slide29:  Source Gradient Climbing A mechanism in the environment may be inducing an environmental gradient field (light, sound source). APFs are used for locating the source with multiple robots. If a robot measures the gradient only in the direction of motion then it can only find minima along a line. An APF enforces the team to stay close and eventually the source will be found. [Ogren, Fiorelli, Leonard 2004] Slide30:  Formation Control Another possibly desirable behavior with a team of mobile systems is to move the entire team in formation. Alternatives such as (l-) or (l-l) control have been considered as basic motion primitives for formations. [Desai, Ostrowski, Kumar 2001] Slide31:  Conclusion Slide32:  Our interest Interested in networks that have the ability to adapt the location of their nodes - not necessarily with autonomous mobility – to solve problems that might require node relocation Do not assume mobility is easily available and inexpensive as it is typically considered in robotics Take into account the cost of mobility and apply it only when it is necessary for the application Slide33:  Sampling-Based Motion Planners An improvement over potential functions in typical robotic applications. They sample the configuration space of robots and construct lower-dimensional representations (e.g. graph structures). They solve path planning problems on the graph structures. Slide34:  Issues to consider Can we apply the SBMP framework to deal with adaptive sensor network problems? Can we have distributed SBMP? Can SBMP plan not just for motion but for other tasks, such as sensing and communication? Can we take into consideration the fact that different tasks have different energy costs? Slide35:  Questions?? THE END

04. 03. 2008
0 views

03. 10. 2007
0 views

04. 10. 2007
0 views

28. 11. 2007
0 views

30. 11. 2007
0 views

03. 12. 2007
0 views

07. 12. 2007
0 views

13. 11. 2007
0 views

14. 11. 2007
0 views

27. 09. 2007
0 views

21. 11. 2007
0 views

29. 12. 2007
0 views

31. 12. 2007
0 views

01. 01. 2008
0 views

02. 01. 2008
0 views

29. 12. 2007
0 views

01. 11. 2007
0 views

19. 12. 2007
0 views

28. 02. 2008
0 views

07. 11. 2007
0 views

06. 03. 2008
0 views

10. 03. 2008
0 views

12. 03. 2008
0 views

14. 03. 2008
0 views

18. 03. 2008
0 views

21. 03. 2008
0 views

26. 03. 2008
0 views

27. 03. 2008
0 views

07. 04. 2008
0 views

30. 03. 2008
0 views

13. 04. 2008
0 views

26. 02. 2008
0 views

07. 11. 2007
0 views

28. 11. 2007
0 views

16. 11. 2007
0 views

24. 02. 2008
0 views