Distributed Sampling-based Planning for Non-Myopic Active Information Gathering
Mariliza Tzes, Yiannis Kantaros and George J. Pappas
IROS 2021, Prague, Czech Republic
Active Information Acquisition
2
Distributed Sampling-based Active Information Gathering - Overview
3
Goal: Design informative paths for a collection of team of robots to reduce uncertainty over a hidden state
Feasible path
Each robot builds its own tree that explores the robot and information space
Every robot holds and updates its own distribution for the hidden state
Explore the robot-motion space through random sampling
Exchange their distributions and
update using Distributed Kalman Filter
Literature Review
4
Hoffmann, G. M., & Tomlin, C. J. (2009). Mobile sensor network control using mutual information methods and particle filters. IEEE Transactions on Automatic Control, 55(1), 32-47.
Dames, Philip, et al. "A decentralized control policy for adaptive information gathering in hazardous environments." 2012 IEEE 51st IEEE Conference on Decision and Control (CDC). IEEE, 2012.
Search-based
Atanasov, Nikolay, et al. "Decentralized active information acquisition: Theory and application to multi-robot SLAM." 2015 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2015.
Sampling-based
Lan, X., & Schwager, M. (2016). Rapidly exploring random cycles: Persistent estimation of spatiotemporal fields with multiple sensing robots. IEEE Transactions on Robotics, 32(5), 1230-1244.
Kantaros, Yiannis, et al. "Asymptotically Optimal Planning for Non-Myopic Multi-Robot Information Gathering." Robotics: Science and Systems. 2019.
Literature Review
5
Hoffmann, G. M., & Tomlin, C. J. (2009). Mobile sensor network control using mutual information methods and particle filters. IEEE Transactions on Automatic Control, 55(1), 32-47.
Dames, Philip, et al. "A decentralized control policy for adaptive information gathering in hazardous environments." 2012 IEEE 51st IEEE Conference on Decision and Control (CDC). IEEE, 2012.
Search-based
Atanasov, Nikolay, et al. "Decentralized active information acquisition: Theory and application to multi-robot SLAM." 2015 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2015.
Sampling-based
Lan, X., & Schwager, M. (2016). Rapidly exploring random cycles: Persistent estimation of spatiotemporal fields with multiple sensing robots. IEEE Transactions on Robotics, 32(5), 1230-1244.
Kantaros, Yiannis, et al. "Asymptotically Optimal Planning for Non-Myopic Multi-Robot Information Gathering." Robotics: Science and Systems. 2019.
Literature Review
6
Hoffmann, G. M., & Tomlin, C. J. (2009). Mobile sensor network control using mutual information methods and particle filters. IEEE Transactions on Automatic Control, 55(1), 32-47.
Dames, Philip, et al. "A decentralized control policy for adaptive information gathering in hazardous environments." 2012 IEEE 51st IEEE Conference on Decision and Control (CDC). IEEE, 2012.
Search-based
Atanasov, Nikolay, et al. "Decentralized active information acquisition: Theory and application to multi-robot SLAM." 2015 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2015.
Sampling-based
Lan, X., & Schwager, M. (2016). Rapidly exploring random cycles: Persistent estimation of spatiotemporal fields with multiple sensing robots. IEEE Transactions on Robotics, 32(5), 1230-1244.
Kantaros, Yiannis, et al. "Asymptotically Optimal Planning for Non-Myopic Multi-Robot Information Gathering." Robotics: Science and Systems. 2019.
Contributions
7
Problem Formulation
8
Robot Dynamics
Hidden State Dynamics
Observation Model
(LiDAR, stereo-camera, bearing sensor)
(target dynamics, environmental field)
finite set of control inputs
Communication - Distributed Kalman Filter
9
3
2
1
neighbors' beliefs and its own observation likelihood function
Active Information Gathering Formulation
10
Goal: Given initial robot states and a prior distribution over the hidden state ,
compute control inputs and a planning horizon F for the optimal problem
information threshold
obstacle avoidance
robot, hidden-state,
observation dynamics
accumulated mutual information
smallest possible time horizon
Active Information Gathering Formulation
11
Goal: Given initial robot states and a prior distribution over the hidden state ,
compute control inputs and a planning horizon F for the optimal problem
Stochastic Control Problem
Deterministic Optimal Control Problem
1. Linear observation dynamics wrt
the hidden state
2. Linear gaussian hidden-state dynamics
a-posteriori covariance matrix of the hidden state
Distributed Kalman Filter
Distributed Active Information Gathering
12
Basic Idea: Each robot builds its own local tree that explores both physical and information space
Two main procedures: (1) Sampling nodes to expand (2) Communication & Extending
the nodes
2. Categorize existing nodes (of the same tree)
based on predefined criteria
(e.g. same robot-state)
1. Each node contains information about
the robot-state, uncertainty, communication-vector
3. Sample a group to expand its nodes
4. Sample a control input from the set of
admissible control inputs
Distributed Active Information Gathering
13
Basic Idea: Each robot builds its own local tree that explores both physical and information space
Two main procedures: (1) Sampling nodes to expand (2) Communication & Extending
the nodes
Apply sampled control input on robot dynamics and
compute new robot states for each node
Distributed AIG – Belief Propagation
14
neighbors' beliefs and its own observation likelihood function
Sample one of the available neighbor’s nodes
The selected sampling functions affect the performance of the algorithm.
We propose biased sampling strategies that bias exploration towards informative areas.
Distributed AIG - Optimality Guarantees
15
Asymptotic Optimality
Probabilistic Completeness
Simulation Results
16
Fully Connected Communication Graph
Sparsely Connected Communication Graph
Scalability Analysis
17
robots
targets
18
Thank you!