Abstract
This work presents a new solution for coordinated search with a team of heterogeneous robots executing a time-critical mission. It is challenging to specify and represent search locations (targets) in known but dynamic environments as well as to find robotic paths to visit the locations. We propose a technique to construct an information map that includes locations of uncertain targets, and generate optimal paths. We especially focus on combining a satellite map that has global coordinates with local images gathered from an aerial robot. Specific targets are represented on a homogeneous coordinate system, so that different types of robots, capable to gather necessary information, may cooperatively conduct a mission. Once a homogeneous map is constructed, a centralized pathfinding algorithm can be applied. Our path-finding algorithm is to choose a set of paths, suggesting a proper number of robots along with their initial locations. In our work, robots can independently travel search locations, which may have dynamics or changes, but collaboratively cover all target locations. Through the experiments with real robotic platforms, we validate the generation of a map including targets and a choice of paths, and compare with existing algorithms.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
R. R. Murphy, K. L. Dreger, S. Newsome, J. Rodocker, B. Slaughter, R. Smith, E. Steimle, T. Kimura, K. Makabe, K. Kon, H. Mizumoto, amd F. Matsuno, S. Tadokoro, and O. Kawase, “Marine heterogeneous multirobot systems at the great eastern Japan tsunami recovery,” Journal of Field Robotics, vol. 29, pp. 819–831, 2012. [click]
D. Floreano and R. J. Wood, “Science, technology and the future of small autonomous drones,” Nature, vol. 521, pp. 460–466, 2015. [click]
J. Hu, L. Xie, K. Y. Lum, and J. Xu, “Multiagent information fusion and cooperative control in target search,” IEEE Transactions on Control Systems Technology, vol. 21, no. 4, pp. 1223–1235, 2013. [click]
S. K. Gan and S. Sukkarieh, “Multi-uav target search using explicit decentralized gradient-based negotiation,” Proc. of IEEE International Conference on Robotics and Automation, 2011, pp. 751–756.
M. Schwager, B. J. Julian, M. Angermann, and D. Rus, “Eyes in the sky: Decentralized control for the deployment of robotic camera networks,” Proceedings of the IEEE, vol. 99, no. 9, pp. 1541–1561, 2011. [click]
Q. Huang, J. Yao, Q. Li, and Y. Zhu, “Cooperative searching strategy for multiple unmanned aerial vehicles based on modified probability map,” in Theory, Methodology, Tools and Applications for Modeling and Simulation of Complex Systems: 16th Asia Simulation Conference and SCS Autumn Simulation Multi-Conference, 2016, pp. 279–287.
S. Weiss, M. Achtelik, L. Kneip, D. Scaramuzza, and R. Siegwart, “Intuitive 3d maps for mav terrain exploration and obstacle avoidance,” Journal of Intelligent & Robotic Systems, vol. 61, no. 1, pp. 473–493, 2011.
L. Heng, G. H. Lee, F. Fraundorfer, and M. Pollefeys, “Real-time photo-realistic 3D mapping for micro aerial vehicles,” Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011, pp. 4012–4019.
M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” Communications of the ACM, vol. 24, no. 6, pp. 381–395, 1981. [click]
D. Scaramuzza, M. C. Achtelik, L. Doitsidis, F. Friedrich, E. Kosmatopoulos, A. Martinelli, M.W. Achtelik, M. Chli, S. Chatzichristofis, L. Kneip, D. Gurdan, L. Heng, G. H. Lee, S. Lynen, M. Pollefeys, A. Renzaglia, R. Siegwart, J. C. Stumpf, P. Tanskanen, C. Troiani, S. Weiss, and L. Meier, “Vision-controlled micro flying robots: From system design to autonomous navigation and mapping in gps-denied environments,” IEEE Robotics Automation Magazine, vol. 21, pp. 26–40, 2014. [click]
F. Fraundorfer, L. Heng, D. Honegger, G. H. Lee, L. Meier, P. Tanskanen, and M. Pollefeys, “Vision-based autonomous mapping and exploration using a quadrotor mav,” Proc. of Int. Conf. on Intelligent Robots and Systems, 2012, pp. 4557–4564.
M. Faessler, F. Fontana, C. Forster, E. Mueggler, M. Pizzoli, and D. Scaramuzza, “Autonomous, vision-based flight and live dense 3D mapping with a quadrotor micro aerial vehicle,” Journal of Field Robotics, vol. 33, no. 4, pp. 431–450, 2016. [click]
S. Arora, “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems,” Journal on the ACM, vol. 45, pp. 753–782, 1998. [click]
D. G. Lowe, “Distinctive image features from scaleinvariant keypoints,” Int. Journal of Computer Vision, vol. 2, no. 60, pp. 91–110, 2004. [click]
A. Vedaldi and B. Fulkerson, “Vlfeat: an open and potable library of computer vision algorithms,” Proc. of Int. Conf. on Multimedia, pp. 1469–1472, 2010.
A. R. Zamir and M. Shah, “Accurate image localization based on Google maps street view,” Proc. of Computer Vision - ECCV 2010: 11th European Conference on Computer Vision, Heraklion, Crete, Greece, Part IV, pp. 255–268, September 5-11, 2010.
P. Agarwal, W. Burgard, and L. Spinello, “Metric localization using google street view,” Proc. of IEEE International Conference on Intelligent Robots and Systems, pp. 3111–3118, 2015.
J. Yuan and A. M. Cheriyadat, “Image feature based gps trace filtering for road network generation and road segmentation,” Machine Vision and Applications, vol. 27, no. 1, pp. 1–12, 2016.
M. Schwager, D. Rus, and J.-J. Slotine, “Unifying geometric, probabilistic, and potential field approaches to multi-robot deployment,” Int. Journal of Robotic Research, vol. 30, pp. 371–383, 2011.
G. Tuna, V. C. Gungor, and K. Gulez, “An autonomous wireless sensor network deployment system using mobile robots for human existence detection in case of disasters,” Ad Hoc Networks, vol. 13, pp. 54–68, 2014. [click]
M. A. Batalin and G. S. Sukhatme, “The design and analysis of an efficient local algorithm for coverage and exploration based on sensor network deployment,” IEEE Trans. on Robotics, vol. 23, pp. 661–675, 2007. [click]
A. Howard, M. J. Matari´c, and G. S. Sukhatme, “An incremental self-deployment algorithm for mobile sensor networks,” Autonomous Robots, vol. 13, pp. 113–126, 2002. [click]
J. L. Ny and G. J. Pappas, “Adaptive deployment of mobile robotic networks,” IEEE Trans. on Automatic Control, vol. 58, pp. 654–666, 2012. [click]
N. Mathew, S. L. Smith, and S. L. Waslander, “A graphbased approach to multi-robot rendezvous for recharging in persistent tasks,” Proc. of the IEEE Int. Conf. on Robotics and Automation, pp. 3497–3502, 2013. [click]
H. J. Min and N. Papanikolopoulos, “The multi-robot coverage problem for optimal coordinated search with an unknown number of robots,” Proc. of IEEE Int. Conf. on Robotics and Automation, 2011.
H. J. Min and N. Papanikolopoulos, “Robot formations using a single camera and entropybased segmentation,” Journal of Intelligent & Robotic Systems, vol. 68, no. 1, pp. 21–41, September 2012. [click]
“Google earth,” https://www.google.com/earth/, accessed: 2017.
Author information
Authors and Affiliations
Corresponding author
Additional information
Recommended by Associate Editor Kyoungchul Kong under the direction of Editor Fuchun Sun. This material is based upon work supported by the BK21 plus program through the National Research Foundation (NRF) funded by the Ministry of Education of Korea.
Hyeun Jeong Min received her Ph.D. degree in Computer Science from the University of Minnesota, USA in 2013. Her research interests include coordinated search, path planning, visual tracking, and robot formation.
Rights and permissions
About this article
Cite this article
Min, H.J. Generating Homogeneous Map with Targets and Paths for Coordinated Search. Int. J. Control Autom. Syst. 16, 834–843 (2018). https://doi.org/10.1007/s12555-016-0742-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12555-016-0742-y