AirLoc MASS 2015

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.


  1. AirLoc: Mobile Robots Assisted Indoor Localization IEEE MASS 2015 Chen Qiu and Matt W. Mutka Dept. of Computer Science and Engineering Michigan State University 2.…
Related documents
  • 1. AirLoc: Mobile Robots Assisted Indoor Localization IEEE MASS 2015 Chen Qiu and Matt W. Mutka Dept. of Computer Science and Engineering Michigan State University
  • 2. Outdoor Localization Indoor Localization Ultrasound WSN RFID Smartphone GPS Location Based Services
  • 3. Smart HomeShopping Mall Cleaner Hospital
  • 4. Simultaneous localization and mapping (SLAM) TurtleBot What does the world look like? Where am I? Sensing Mapping Filtering Constraint: can Not locate people’s positions
  • 5. Everyone has a smartphone
  • 6. Dead Reckoning S1 S2 Sn Sn−1ax X Y Z ay az Smartphone Based Indoor Localization Smartphone’s Acceleration Not Equal to User’s body Acceleration Error Accumulation 0.5 degree error of orientation sensor 308m error within 1 minute Imperfection
  • 7. Conjecture: Could mobile robots assist Indoor localization ? Smartphone based indoor positioning • Dead Reckoning • Finger Printing / Radio Map • Other Inertial Sensing (Light, Sound, Barometer) Mobile Robot • Low cost (TurtleBot) • Accurate Position (Error within 0.3m) • Extra Services
  • 8. 0 5 10 15 20 25 30 35 40 0 10 20 30 40 50 Time (seconds) Deviation Distance(meters) Confidence interval Confidence interval Deviations without calibration Deviations with calibration Receive Accurate Location Message (X,Y)& (X,Y)& (X,Y)& (X,Y)& Building Connection RSSI>Threshold Scanning Devices Sending Location Messages Preliminary Observation Sending Accurate Location Information
  • 9. Goal of System Design: Mobile Robot send more accurate location to smartphones Serving Routes Selection: First Serve the places with more people More Robots, Fast Robots: System Costs, Equipments limitation Sensing Range: Bluetooth (~10m), WiFi (Energy Concern) Potential Resolutions: Sampling Frequency: Cannot Define on Smartphone, Energy Consume
  • 10. Crowd Density Estimation Common Phenomenon: RSSI variation caused by human bodies 3. density levels for generating routes 1. collect features on each sub-grid High Density Level Normal Density Level Low Density Level 2. cluster samples Steps of Estimation: Feature 1: Num of Devices Feature 2: Bluetooth RSSI K-Means EM First Serve Higher Density
  • 11. Problem Formulation Node Edge Room Hallway Graph Indoor Map
  • 12. Robot’s Traveling Strategy Traveling Salesman Problem (TSP): • Find the best way to visit all the cities • Minimal travel time • NP-hard Problem AirLoc focuses on time cost of routes and rooms Edge Based Algorithm (EBA): • Both edges and nodes are assigned weights • Dynamic Programming to find the route with minimal travel time • Approximate solution (NP-hard Reduction)
  • 13. Edge Based Algorithm (EBA) R1(HD) R5(LD) R4(HD)R3(LD) R2(MD) 1.5min 2min 0.5min 1min LD – Low Density 0.5m in0.5m in 0.5m in 0.5m in 0.5m in 0.5m in MD – Medium Density HD – High Density – Delete after round 1 – Delete after round 2
  • 14. Parallel Function 1: Computing Serving Routes Density Levels Serving Routes Clustering Dynamic Programming RSSI Collection (X,Y)& (X,Y)& (X,Y)& (X,Y)& Moving Robot Known Map Mobile APP Parallel!Function 2: Sending Accurate Location Information Building Connection RSSI>Threshold 1. Bluetooth RSSI 2. Number of Devices Scanning Devices Sending Location Messages Overview of Single Robot Based System
  • 15. Multi-robots System Design Single robot is not enough Environment with more rooms Crowd density is dynamic More robots, better accuracy Multi-robot design strategy
  • 16. Two-robots System Design Partition the graph to two components Principle: allocate more time to higher density rooms Trade off between Distance and Density Principle: balance between the two aspects Principle: limit the time costs on the edges Density First Algorithm (DenFA) Distance First Algorithm (DisFA) Distance/Density First Algorithm (DDFA)
  • 17. 1 0 0 2 1 8 8 9 Density First Algorithm (DenFA) X axis Yaxis Merge to Low Density Area
  • 18. 1 0 0 2 1 8 8 9 Distance First Algorithm (DisFA) X axis Yaxis Merge to High Density Area
  • 19. Distance/Density First Algorithm (DDFA) Combine DisFA and DenFA Keep Connectivity in each component Use thresholds to assign weights T1 and T2 , Distance First T1 and T2 , Density First
  • 20. Low Density AreaHigh Density Area nLDA nHDA ≤10% Preemption Period: 21 % 2n % 22 % 23 % nLDA nHDA >10% Exponential growth Preemption: make robots more efficiency
  • 21. Low Density AreaHigh Density Area Preemption Period: nLDA nHDA >10% Return to Initial State 20 % Preemption: make robots more efficiency
  • 22. Extend two robots to multi-robots - Higher Crowd Density Area Unbalance Serving Tree Number of Devices AverageRSSI(%) Room i Allocate robots to HDA(P ×θ) /(θ +1) Allocate robots to LDAP − (P ×θ) / (θ +1) θ = ( ωi i=1 H ∑ ) /( ω j j=1 L ∑ ) Definition of ω P - num of robots
  • 23. Extend Two Robots to Multi-robots How robots go back to the root ? Return by the way you came Dynamic Return Approach Find node k: the smallest sum of distances between k and other rooms Arrange k as the “new” root min( Dist j=1 n ∑ i=1 n ∑ (i, j)) crowd density change, waste time
  • 24. AirLoc System Evaluation Experiment Setting •The height of the tablet is 1 meter •The speed of is 0.3m /s •0-6 volunteers carry Samsung Galaxy 4 or Google Nexus Tablet •Employ on Bluetooth Adapter to communicate •Volunteers in the experimental environment walk freely Metrics Deviation Distance: Euclidean Distance (meter) L(x) = − P(xi )log2 (P(xi )) i=1 m ∑Location Entropy:
  • 25. Data Collection in Indoor Building Data collected in a room Data collected in a hallway - Robot Calibration - Smartphone Position Data samples on the map
  • 26. 1 2 3 1 4 5 7 8 9 10 11 12 13 14 15 16 17 2 3 4 5 8 7 6 10 1112 15 14 13 16 18 19 21 20 22 24 23 25 17 Ground Truth Estimated Trace 20 19 18 23 22 21 2524 R1 R1 R2 R1 R3 - Send Location Message - Sequence Num of RobotR# - Calibrate Deviation 1100’s Floor Plan R3 Cloud Server 9 Single Trace Study in Real Floorpan • Calibrated by robots, the errors are reduced • Dead reckoning yields obvious deviations • Mobile robots update the crowd density in a cloud Conclusion:
  • 27. T Slot S Slot R Slot T Slot … … Update Density Levels Form Final Serving AreaDivide Groups Loop OPOS (One Period One Sample): T Slot OPMS (One Period Multiple Sample): T Slot & S Slot Static crowd density: initial state Crowd Density Updating Conclusion: • Multi-robots update crowd density continuously • Real Time crowd density improves the localization results Duty cycle of AirLoc Compare different density information 2 4 6 8 200 300 400 500 600 Number of rounds Numberof deviationgrids OPMS crowd density Static crowd density OPOS crowd density
  • 28. 0 2 4 6 8 10 12 0 0.2 0.4 0.6 Number of rounds LocationEntropy BalanceTree−Dynamic Return BalanceTree−Static Return UnblanceTree−Static Return UnblanceTree−Dynamic Return 1 2 3 4 5 6 0 50 100 Number of smartphones AverageRSS(%) Low Density Level High Density Level Normal Density Level Centroids of clusters 1 2 3 4 5 6 100 200 300 400 500 Average degree of nodes Numberof deviationgrids 32 Robots 8 Robots EBA Evaluation Results Cluster different density levels for all the rooms Unbalanced Tree outperforms Balance Tree Dynamic Return enhances AirLoc More robots provide more accuracy
  • 29. Summary • Mobile robots interact with smartphones to send accurate location information • AirLoc organizes multi-robots for improving the smartphones’ positioning information • Single robot adopts Edge Based Algorithm (EBA) to generate the optimized serving route • AirLoc updates the crowd density levels continuously Distance/Density First Algorithm Dynamic Return PreemptionUnbalanced Serving Tree
  • 30. Thank you ! Questions ?
  • Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks