Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Robot algorithms for localization of multiple emission sources

Published: 29 April 2011 Publication History

Abstract

The problem of time-varying, multisource localization using robotic swarms has received relatively little attention when compared to single-source localization. It involves distinct challenges regarding how to partition the robots during search to ensure that all sources are located in minimal time, how to avoid obstacles and other robots, and how to proceed after each source is found. Unfortunately, no common set of validation problems and reference algorithms has evolved, and there are no general theoretical foundations that guarantee progress, convergence, and termination. This article surveys the current multisource literature from the viewpoint of these central questions.

References

[1]
Arulampalam, M. S., Maskell, S., Gordon, N., and Clapp, T. 2002. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Trans. Signal Proc. 50, 2, 174--188.
[2]
Bachmayer, R. and Leonard, N. E. 2002. Vehicle networks for gradient descent in a sampled environment. In Proceedings of the 41stIEEE Conference on Decision and Control. 1--6.
[3]
Barlow, G. J., Choong, K. O., and Smith, S. F. 2008. Evolving cooperative control on sparsely distributed tasks for UAV teams without global communication. In Proceedings of the Genetic and Evolutionary Computation Conference. 177--184.
[4]
Baudoin, Y., Acheroy, M., Piette, M., and Salmon J. P. 1999. Humanitarian demining and robotics. J. Mine Act. Foc. Mach. Assist. Demin. 3, 2, 433--435.
[5]
Bell, W. J. and Tobin, T. R. 1982. Chemo-orientation. Biolog. Rev. Cambridge Phil. Soc. 57, 219--260.
[6]
Borah, D. and Balagopal, A. 2004. Localization and tracking of multiple near-field sources using randomly distributed sensors. In Proceedings of the 38th Asilomar Conference on Signals, Systems, and Computers. 1323--1327.
[7]
Cortes, J. and Bullo, F. 2009. Nonsmooth coordination and geometric optimization via distributed dynamical systems. SIAM Rev. 51, 1, 163--189.
[8]
Cortes, J., Martinez, S., Karatax, T., and Bullo, F. 2004. Coverage control for mobile sensing networks. IEEE Trans. Robot. Automat. 20, 2, 243--255.
[9]
Cui, X., Hardin, C. T., Ragade, R. K., and Elmaghraby, A. S. 2004a. A swarm approach for emission sources localization. In Proceedings of the 16th International Conference on Tools with Artificial Intelligence. 424--430.
[10]
Cui, X., Hardin, C. T., Ragade, R. K., and Elmaghraby, A. S. 2004b. A swarm-based fuzzy logic control mobile sensor network for hazardous contaminants localization. In Proceedings of the International Conference on Mobile Ad-hoc and Sensor Systems. 194--203.
[11]
Cui, X., Ragade, R. K., and Elmaghraby, A. S. 2004c. A collaborative search and engage strategy for multiple mobile agents with local communication in large scale hostile area. In Proceedings of the International Symposium on Collaborative Technologies and Systems. 244--249.
[12]
Dhariwal, A., Suhkatme, G. S., and Requicha, A. A. G. 2004. Bacterium-inspired robots for environmental monitoring. In Proceedings of the International conference on Robotics and Automation. 1436--1443.
[13]
DoD. 2007. Office of the Secretary of Defense Unmanned Systems Roadmap (2007--2032). Department of Defense, Washington, DC.
[14]
Farrel, J. A., Pang, S., and Li, W. 2003. Plume mapping via hidden markov methods. IEEE Trans. Syst. Man Cybernet.—Part B: Cybernetics, 33, 6, 850--863.
[15]
Ferri, G., Jakuba, M. V., Caselli, E., Mattoli, V., Mazzolai, B., Yoerger, D. R., and Dario, P. 2007. Localizing multiple gas/odor sources in an indoor environment using Bayesian occupancy grid mapping. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. 566--571.
[16]
Ferri, G, Caselli, E., Mattoli, V., Mondini, A., Mazzolai, B., and Dario, P. 2006. A biologically-inspired algorithm implemented on a new highly flexible multi-agent platform for gas source localization. In Proceedings of the 1stIEEE/RAS-EMBS International Conference on Biomedical Robotics and Biomechatronics. 573--578.
[17]
Fiorelli, E., Bhatta, P., Leonard, N. E., and Shulman, I. 2003. Adaptive sampling using feedback control of an autonomous underwater glider fleet. In Proceedings of the 13th International Symposium on Unmanned Untethered Submersible Technology. 1--16.
[18]
Gazi, V. and Passino, K. 2004. Stability analysis of social foraging swarms. IEEE Trans. Syst. Man Cybernet.—Part B: Cybernetics, 34, 1, 539--557.
[19]
Gehrig, T. and McDonough, J. 2007. Tracking multiple speakers with probabilistic data association filters. In Multimodal Technologies for Perception of Humans. Lecture Notes in Computer Science, vol. 4122, Springer, Berlin, Germany, 137--150.
[20]
GICHD. 2002. Mine Action Equipment: Study of Global Operational Needs. Geneva International Centre for Humanitarian Demining, Geneva, Switzerland.
[21]
Grewal, M. S. and Andrews, A. P. 1993. Kalman Filtering Theory and Practice. Prentice Hall, Upper Saddle River, NJ.
[22]
Griffiths, D. 1999. Introduction to Electrodynamics. Prentice Hall, Upper Saddle River, NJ.
[23]
Hayes, A. T., Martinoli, A., and Goodman, R. M. 2002. Distributed odor source Localization. IEEE Sens. J. 2, 3, 260--271.
[24]
Hinze, J. 1975. Turbulence. McGraw-Hill, New York, NY.
[25]
Hogg, T. 2007. Coordinating microscopic robots in viscous fluids. Auton. Agent Multi-Agent Syst. 14, 217--305.
[26]
Holland, O. and Melhuish, C. 1996. Some adaptive movements of animats with single symmetrical sensors. In Proceedings of the 4thConference on Simulation and Adaptive Behavior—From Animals to Animats. 55--64.
[27]
Howard, A., Mataric, M., and Sukhatme, G. 2002. Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem. In Proceedings of the 6thInternational Symposium on Distributed Autonomous Robotics Systems. 299--208.
[28]
Jakuba, M. V. 2007. Stochastic mapping for chemical plume source localization with application to autonomous hydrothermal vent discovery. PhD dissertation. Massachussetts Institude of Technology and Woods Hole Oceanographic Institution, Cambridge and Woods Hole, MA.
[29]
Kamath, S., Meisner, E., and Isler, V. 2007. Triangulation based multi target tracking with mobile sensor networks. In Proceedings of the IEEE International Conference on Robotics and Automation. 3283--3288.
[30]
Kennedy, J. and Eberhart, R. C. 1995. Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks. 1942--1948.
[31]
Kowadlo, G. and Russell, R. A. 2008. Robot odor localization: A taxonomy and survey. Int. J. Robot. Res. 27, 869--894.
[32]
Krishnanand, K. N., Amruth, P., Guruprasad, M. H., Bidargaddi, S. V., and Ghose, D. 2006a. Rendezvous of glowworm-inspired robot swarms at multiple source locations: A sound source based real-robot implementation. In Ant Colony Optimization and Swarm Intelligence, Proceedings of the 5thInternational Workshop, M. Dorigo, L. M. Gambardella, M. Brattari, A. Martinoli, R. Poli, and Th. Stützle, Eds. Lecture Notes in Computer Science, vol. 4150. Springer, Berlin, Germany, 259--269.
[33]
Krishnanand, K. N., Amruth, P., Guruprasad, M. H., Bidargaddi, S. V., and Ghose, D. 2006b. Glowworm-inspired robot swarm for simultaneous taxis towards multiple radiation sources. In Proceedings of the IEEE International Conference on Robotics and Automation. 958--963.
[34]
Krishnanand, K. N. and Ghose, D. 2005. Detection of multiple source locations using a glowworm metaphor with application to collective robotics. In Proceedings of the IEEE Swarm Intelligence Symposium. 84--91.
[35]
Krishnanand, K. N. and Ghose, D. 2006. Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications. Multiagent Grid Syst. 2, 3, 209--222.
[36]
Krishnanand, K. N. and Ghose, D. 2007. Glowworm swarm optimization: A swarm intelligence based multimodal function optimization technique with applications to multiple signal source localization, Tech. rep. GCDSL 2007/05. Department of Aerospace Engineering, Indian Institute of Science, Bangalore, India.
[37]
Krishnanand, K. N. and Ghose, D. 2008. Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations. Robot. Auton. Syst. 56, 7, 549--569.
[38]
Krishnanand, K. N. and Ghose, D. 2009a. A glowworm swarm optimization based multi-robot system for signal source localization. In Design and Control of Intelligent Robotic Systems: SCI 177. D. Liu, L. Wang, and K. C. Tan, Eds. Springer Verlag, Berlin, Germany, 49--68.
[39]
Krishnanand, K. N. and Ghose, D. 2009b. Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions. Swarm Intell. 3, 2, 87--124.
[40]
Kullback, S. 1987. The Kullback-Leibler distance. Amer. Stat. 41, 340--341.
[41]
Larcombe, M. H. E. and Helsall, J. R. 1984. Robotics in Nuclear Engineering: Computer Assisted Teleoperation in Hazardous Environments with Particular Reference to Radiation Fields. Kluwer Academic Publishers, Norwell, MA.
[42]
Lavalle, S. M. 1998. Rapidly-exploring random trees: a new tool for path planning. Res. rep. TR 98-11. Computer Science Dept., Iowa State University, Ames, Iowa.
[43]
Lewis, R. 1986. Optimal Estimation with an Introduction to Stochastic Control Theory. John Wiley & Sons, New York, NY.
[44]
Lilienthal, A. and Duckett, T. 2003. Creating gas concentration gridmaps with a mobile robot. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. 118--123.
[45]
Lilienthal, A., Reimann, D., and Zell, A. 2003. Gas source tracing with a mobile robot using an adapted moth strategy. In Proceedings of the IEEE International Conference on Robotics and Automation. 150--160.
[46]
Liu, Y. and Passino, K. M. 2002. Biomimicry of social foraging bacteria for distributed optimization: Models, principles, and emergent behaviors. J. Opt. Theor. Appl. 115, 3, 603--628.
[47]
Lochmatter, T., Raemy, X., and Martinoli, A. 2007. Odor source localization with mobile robots. Bull. Swiss Soc. Aut. Contr. 46, 11--14.
[48]
Luke, S., Sullivan, K., Panait, L., and Balan, G. 2005. Tunably decentralized algorithms for cooperative target observation. In Proceedings of the International Conference of Autonomous Agents and Multi-agent Systems. 911--917.
[49]
Lytridis, C., Virk, G. S., and Kadar, E. E. 2004. Co-operative smell-based navigation for mobile robots. In Proceedings of the 7thInternational Conference on Climbing and Walking Robots. 1107--1117.
[50]
Marques, L., Nunes, U., and De Almeida, A. 2002. Olfaction-based mobile robot navigation. Thin Sol. Films, 418, 1, 51--58.
[51]
Marques, L., Nunes, U., and De Almeida, A. 2003. Odour searching with autonomous mobile robots: An evolutionary-based approach. In Proceedings of the IEEE International Conference on Advanced Robotics. 494--500.
[52]
Marques, L., Nunes, U., and De Almeida, A. T. 2006. Particle swarm-based olfactory guided search. Auton. Robot. 20, 277--287.
[53]
McGill, K. and Taylor, S. 2009a. Comparing swarm algorithms for multi-source localization. In Proceedings of the IEEE International Workshop on Safety, Security, and Rescue Robotics.
[54]
McGill, K. and Taylor, S. 2009b. Comparing swarm algorithms for large scale multi-source localization. In Proceedings of the IEEE International Conference on Technologies for Practical Robot Applications.
[55]
Mennitt, D., Gillett, P., Carneal, J., and Johnson, M. 2006. Tracking noise sources using multiple mobile microphone arrays. In Proceedings of the 13th International Congress on Sound and Vibration.
[56]
Mitchell, T. 1997. Machine Learning. McGraw-Hill, New York, NY.
[57]
Murlis, J., Elkinton, J., and Carde, R. 1992. Odor plumes and how insects use them. Ann. Rev. Entomol. 37, 1, 505--532.
[58]
Murphy, K. P., Weiss, Y., and Jordan, M. I. 1999. Loopy belief propagation for approximate inference: An empirical study. In Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence. 467--475.
[59]
Murphy, R. R. Rescue robots at the World Trade Center. 2003. J. Japan Soc. Mech. Eng. 102, 1019, 794--802.
[60]
NIH. 2008. National Institutes of Health Roadmap for Medical Research: Nanomedicine. http://nihroadmap.nih.gov/nanomedicine/.
[61]
Ogren, P., Fiorelli, E., and Leonard, N. E. 2004. Cooperative control of mobile sensor networks: adaptive gradient climbing in a distributed environment. IEEE Trans. Aut. Contr. 49, 8, 1291--1302.
[62]
Oh, S., Hwang, I., Roy, K., and Sastry, S. 2005. A fully automated distributed multiple-target tracking and identity management algorithm. In Proceedings of the AIAA Guidance, Navigation, and Control Conference.
[63]
Oh, S., Russell, S., and Sastry, S. 2004. Markov chain Monte Carlo data association for general multiple-target tracking problems. In Proceedings of the 43rdIEEE Conference on Decision and Control. 735--742.
[64]
Olfati-Saber, R. 2006. Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Trans. Aut. Contr. 51, 3, 401--420.
[65]
Olfati-Saber, R. 2007. Distributed tracking for mobile sensor networks with information-driven mobility. In Proceedings of the American Control Conference. 4606--4612.
[66]
Pang, S. and Farrell, J. A. 2006. Chemical plume source localization. IEEE Trans. Syst. Man Cybernet.—Part B: Cybernet. 36, 5, 1068--1080.
[67]
Passino, K. M. 2002. Biomimicry of bacterial foraging for distributed optimization and control. IEEE Contr. Syst. Mag. 22, 3, 52--67.
[68]
Pugh, J. and Martinoli, A. 2008. Distributed adaptation in multi-robot search using particle swarm optimization. In Proceedings of the 10th International Conference on the Simulation of Adaptive Behavior. 393--402.
[69]
Rahimi, M., Pon, R., Kaiser, W. J., Sukhatme, G. S., Estrin, D., and Srivastava, M. 2004. Adaptive Sampling for Environmental Robotics. In Proceedings of the International Conference on Robotics and Automation. 3537--3544.
[70]
Ristic, B., Morelande, M., and Gunatilaka, A. 2008. A controlled search for radioactive point sources. In Proceedings of the International Conference on Information Fusion. 1--5.
[71]
Rozas, R., Morales, J., and Vega, D. 1991. Artificial smell detection for robotic navigation. In Proceedings of the 5thInternational Conference on Advanced Robotics. 1730--1733.
[72]
Russell, R. 2003. Chemical source location and the robomole project. In Proceedings of the Australasian Conference on Robotics and Automation. 1--6.
[73]
Russell, R., Bab-Hadiashar, A., Shepherd, R., and Wallace, G. 2003. A comparison of reactive chemotaxis algorithms. Robot. Autonom. Syst. 45, 83--97.
[74]
Sandini, G., Lucarini, G., and Varoli, M. 1993. Gradient driven self organized systems. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. 429--432.
[75]
Scerri, P., Glinton, R., Owens, S., Scerri, D., and Sycara, K. 2007. Geolocation of RF emitters by many UAVs. In Proceedings of the AIAA Infotech@Aerospace Conference and Exhibit. 1--13.
[76]
Scerri, P., von Gonten, T., Fudge, G., Owens, S., and Sycara, K. 2008. Transitioning multiagent technology to UAV applications. In Proceedings of 7thInternational Conference on Autonomous Agents and Multiagent Systems. 89--96.
[77]
Sheng, X. and Hu, Y. 2004. Sequential acoustic energy based source localization using particle filter in a distributed sensor network. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. 972--975.
[78]
Sheng, X. and Hu, Y. 2005a. Distributed particle filters for wireless sensor network target tracking. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. 845--848.
[79]
Sheng, X. and Hu, Y. 2005b. Distributed particle filter with GMM approximation for multiple targets localization and tracking in wireless sensor network. In Proceedings of the 4thInternational Symposium on Information Processing in Sensor Networks.
[80]
Sibley, G. T., Rahimi, M. H., and Sukhatme, G. S. 2002. A tiny mobile robot platform for large-scale sensor networks. In Proceedings of the IEEE International Conference on Robotics and Automation.
[81]
Spears, D., Kerr, W., and Spears, W. 2006. Physics-based robot swarms for coverage problems. Int. J. Intell. Contr. Syst. 11, 3, 124--140.
[82]
Spears, W., Spears, D., Hamann, J., and Heil, R. 2004. Distributed, physics-based control of swarms and vehicles. Auton. Robots, 17, 2-3, 137--162.
[83]
Tadokoro, S., Takmori, T., Osuka, K., and Tsurutani, S. 2000. Investigation report of the rescue problem at Hanshin-Awaji earthquake in Kobe. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. 1880--1885.
[84]
Terry, D., Bader, J., and Messina, M. 1999. Simulated annealing search algorithm for the determination of activation energies and Arrhenius prefactors from limited experimental kinetic data. J. Chem. Inf. Comp. Sci. 39, 1204--1210.
[85]
Vergassola, M., Villermaux, E., and Shraiman, B. I. 2007. ‘Infotaxis’ as a strategy for searching without gradients. Nature, 445, 406--409.
[86]
Virk, G. S. and Kadar, E. E. 1998. Co-operative navigation for target searching in a diffusion field. In Proceedings of the IEEE International Conference on Control Applications. 423--427.
[87]
Wainwright, M., Jaakkola, T., and Willsky, A. 2003. Tree-reweighted belief propagation algorithms and approximate ml estimation via pseudo-moment matching. In Proceedings of the Conference on Artificial Intelligence and Statistics.
[88]
Wang, H. and Guo, Y. 2008. A decentralized control for mobile sensor network effective coverage. In Proceedings of the 7thWorld Congress on Intelligent Control and Automation. 473--478.
[89]
Zarzhitsky, D., Spears, D., and Spears, W. 2005. Swarms for chemical plume tracing. In Proceedings of the Swarm Intelligence Symposium. 249--256.
[90]
Zhang, Q., Sobelman, G., and He, T. 2009. Gradient-based target localization in robotic sensor networks. Pervas. Mobile Comp. 5, 1, 37--48.
[91]
Zou, Y. and Chakrabarty, K. 2007. Distributed mobility management for target tracking in mobile sensor networks. IEEE Trans. Mob. Comp. 6, 8, 872--887.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys
ACM Computing Surveys  Volume 43, Issue 3
April 2011
466 pages
ISSN:0360-0300
EISSN:1557-7341
DOI:10.1145/1922649
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 April 2011
Accepted: 01 September 2009
Revised: 01 May 2009
Received: 01 December 2008
Published in CSUR Volume 43, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Bayesian filters
  2. Bayesian occupancy mapping
  3. Source localization
  4. biologically inspired algorithms
  5. hill-climbing algorithms
  6. mobile robotic networks
  7. swarm algorithms

Qualifiers

  • Research-article
  • Research
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)16
  • Downloads (Last 6 weeks)0
Reflects downloads up to 29 Sep 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Localizing multiple radiation sources actively with a particle filterNuclear Engineering and Technology10.1016/j.net.2024.08.040Online publication date: Sep-2024
  • (2020)A Physarum-Inspired Decision-Making Strategy for Multisource Task Searching of Mobile RobotsComplexity10.1155/2020/31581562020(1-14)Online publication date: 21-Sep-2020
  • (2020)Swarm Robots Search for Multiple TargetsIEEE Access10.1109/ACCESS.2020.2994151(1-1)Online publication date: 2020
  • (2020)Real-time gas recognition and gas unmixing in robot applicationsSensors and Actuators B: Chemical10.1016/j.snb.2020.129111(129111)Online publication date: Oct-2020
  • (2017)A Fast CUDA-Based Implementation for the Euclidean Distance Transform2017 International Conference on High Performance Computing & Simulation (HPCS)10.1109/HPCS.2017.123(815-818)Online publication date: Jul-2017
  • (2017)Generation of rhythmic hand movements in humanoid robots by a neural imitation learning architectureBiologically Inspired Cognitive Architectures10.1016/j.bica.2016.07.00219(39-48)Online publication date: Jan-2017
  • (2016)Gathering Bearing Data for Target LocalizationIEEE Robotics and Automation Letters10.1109/LRA.2016.25213871:1(369-374)Online publication date: Jan-2016
  • (2016)Active localization of VHF collared animals with aerial robots2016 IEEE International Conference on Automation Science and Engineering (CASE)10.1109/COASE.2016.7743503(934-939)Online publication date: Aug-2016
  • (2016)Search and tracking algorithms for swarms of robotsRobotics and Autonomous Systems10.1016/j.robot.2015.08.01075:PB(422-434)Online publication date: 1-Jan-2016
  • (2014)Development of a Robotic Platform to Implement a Boundary Mapping AlgorithmIFAC Proceedings Volumes10.3182/20140313-3-IN-3024.0016547:1(484-490)Online publication date: 2014
  • Show More Cited By

View Options

Get Access

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media