Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-02T23:52:40.915Z Has data issue: false hasContentIssue false
  • English
  • Français

Adaptive source search in a gradient field

Published online by Cambridge University Press:  25 April 2014

Xiaochen Zhang ,
Yi Sun  and
Jizhong Xiao
Xiaochen Zhang
Affiliation:
Department of Electrical Engineering, The City College of New York, New York, USA
Yi Sun*
Affiliation:
Department of Electrical Engineering, The City College of New York, New York, USA
Jizhong Xiao
Affiliation:
Department of Electrical Engineering, The City College of New York, New York, USA
*
*Corresponding author. Email: [email protected].
Get access Rights & Permissions [Opens in a new window]

Summary

Most existing source search algorithms suffer from a high travel cost, and few of them have been analyzed in performance in noisy environments where local basins are presented. In this paper, the theseus gradient search (TGS) is proposed to effectively overcome local basins in search. Analytical performances of TGS and the gradient ascend with correlated random walk (GACRW), which is a variant of correlated random walk, are derived and compared. A gradient field model is proposed as an analytical tool that makes it feasible to analyze the performances. The analytical average searching costs of GACRW and TGS are obtained for the first time for this class of algorithms in the environments with local basins. The costs, expressed as functions of searching space size, local basin size, and local basin number are confirmed by simulation results. The performances of GACRW, TGS, and two chemotaxis algorithms are compared in the gradient field and a scenario of indoor radio source search in a hallway driven by real data of signal strengths. The results illustrate that GACRW and TGS are robust to noisy gradients and are more competitive than the chemotaxis-based algorithms in real applications. Both analytical and simulation results indicate that in the presence of local basins, TGS almost always costs the lowest.

Keywords

Biased and correlated random walkGradient ascendLocal maximumSelf-avoiding walk
Type
Articles
Information
Robotica , Volume 33 , Issue 8 , October 2015 , pp. 1589 - 1608
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Adler, J., “Chemotaxis in bacteria,” Science 153 (3737), 708–716 (1966).Google Scholar
2. Adler, J., “The sensing of chemicals by bacteria,” Sci. Am. 234 (4), 40–47 (1976).Google Scholar
3. Atema, J., “Eddy chemotaxis and odor landscapes: Exploration of nature with animal sensors,” Biol. Bull. 191, 129–139 (Aug. 1996).Google Scholar
4. Berg, H. C., E. Coli in Motion (Springer, Berlin, Germany, 2004).Google Scholar
5. Byers, J. A., “Correlated random walk equations of animal dispersal resolved by simulation,” Ecology 82 (6), 1680–1690 (Jun. 2001).Google Scholar
6. Chong, E. K. P. and Zak, S. H., An Introduction to Optimization, 2nd ed. (Wiley-Interscience, River Street Hoboken, NJ, 2001).Google Scholar
7. Codling, E. A., Plank, M. J. and Benhamou, S., “Random walk models in biology,” J. R. Soc. Interface 5 (25), 813–834 (Aug. 2008).Google Scholar
8. Cowlagi, R. and Tsiotras, P., “Multiresolution motion planning for autonomous agents via wavelet-based cell decompositions,” IEEE Trans. Syst. Man Cybern. 42 (5), 1455–1469 (Oct. 2012).Google Scholar
9. Lloyd, E. H., “What is, and what is not, a Markov chain?,” J. Hydrol. 22 (1–2), 1–28 (1974).Google Scholar
10. Fraenkel, G. S. and Gunn, D. L., The Orientation of Animals: Kineses, Taxes and Compass Reactions (Dover, Kent, UK, 1961).Google Scholar
11. Grinstead, C. M. and Snell, L. J., Introduction to Probability (American Mathematical Society, Providence, RI, 2006).Google Scholar
12. Holland, O. and Melhuish, C., “Some Adaptive Movements of Animats with Single Symmetrical Sensors,” In: From Animals to Animats, (Maes, P., Mataric, M., Meyer, J., Pollack, J. and Wilson, S., eds) vol. 4 (MIT Press, Cambridge, UK, 1996) pp. 55–64.Google Scholar
13. Ishida, H., Suetsugu, K., Nakamoto, T. and Moriizumi, T., “Study of autonomous mobile sensing system for localization of odor source using gas sensors and anemometric sensors,” Sensors Actuators A 45 (2), 153–157 (1994).Google Scholar
14. Jin, X. and Ray, A., “Coverage Control of Autonomous Vehicles for Oil Spill Cleaning in Dynamic and Uncertain Environments,” American Control Conference (ACC), 2013, Washington, DC, USA. (Jun. 2013) pp. 2594–2599.Google Scholar
15. Jin, X. and Ray, A., “Navigation of autonomous vehicles for oil spill cleaning in dynamic and uncertain environments,” Int. J. Control, 87 (4), 1–15 (2014).Google Scholar
16. Johnson, D. S., London, J. M., Lea, M.-A. and Durban, J. W., “Continuous-time correlated random walk model for animal telemetry data,” Ecology 89 (5), 1208–1215 (May 2008).Google Scholar
17. Kareiva, P. M. and Shigesada, N., “Analyzing insect movement as a correlated random walk,” Oecologia 56, 234–238 (1983).Google Scholar
18. Kowadlo, G. and Russell, R. A., “Robot odor localization: A taxonomy and survey,” Int. J. Robot. Res. 27 (8), 869–894 (2008).Google Scholar
19. Marques, L., Nunes, U. and de Almeida, A. T., “Olfaction-based mobile robot navigation,” Thin Solid Films 418 (1), 51–58 (2002).Google Scholar
20. Nurzaman, S. G., Matsumoto, Y., Nakamura, Y., Koizumi, S. and Ishiguro, H., “Yuragi-Based Adaptive Searching Behavior in Mobile Robot: From Bacterial Chemotaxis to Levy Walk,” IEEE International Conference on Robotics and Biomimetics, 2008, Bangkok, Thailand. (22–25 Feb. 2009) pp. 806–811.Google Scholar
21. Park, W., Liu, Y., Zhou, Y., Moses, M. and Chirikjian, G. S., “Kinematic state estimation and motion planning for stochastic nonholonomic systems using the exponential map,” Robotica 26 (4), 419–434 (2008).Google Scholar
22. Patlak, C. S., “A mathematical contribution to the study of orientation of organisms,” Bull. Math. Biophys. 15 (4) (1953), 431–476.Google Scholar
23. Patlak, C. S., “Random walk with persistence and external bias,” Bull. Math. Biophys. 15 (3), 311–338 (1953).Google Scholar
24. Pearson, K., “The problem of the random walk,” Nature 72 (1865), 294 (1905).Google Scholar
25. Porat, B. and Nehorai, A., “Localizing vapor-emitting sources by moving sensors,” IEEE Trans. Signal Process. 44 (4), 1018–1021 (1996).Google Scholar
26. Russell, R., Hadiashar, B.-A., Shepherd, R. L. and Wallace, G. G., “A comparison of reactive robot chemotaxis algorithms,” Robot. Auton. Syst. 45 (2), 83–97 (2003).Google Scholar
27. Russell, R. A., “Robotic location of underground chemical sources,” Robotica 22 (1), 109–115 (2004).Google Scholar
28. Russell, R. A., Thiel, D., Deveza, R. and Mackay-sim, A., “A Robotic System to Locate Hazardous Chemical Leaks,” Proceedings of the IEEE International Conference on Robotics and Automation, Nagoya, Japan. (21–27 May 1995), pp. 556–561.Google Scholar
29. Sims, D. W., Southall, E. J., Humphries, N. E., Hays, G. C., Bradshaw, C. J. A., Pitchford, J. W., James, A., Ahmed, M. Z., Brierley, A. S., Hindell, M. A., Morritt, D., Musyl, M. K., Righton, D., Shepard, E. L. C., Wearmouth, V. J., Wilson, R. P., Witt, M. J., and Metcalfe, J. D., “Scaling laws of marine predator search behaviour,” Nature 451 (7182), 1098–1102 (Feb. 2008).Google Scholar
30. Song, D., Kim, C.-Y. and Yi, J., “Monte Carlo Simultaneous Localization of Multiple Unknown Transient Radio Sources Using a Mobile Robot with a Directional Antenna,” IEEE International Conference on Robotics and Automation, 2009, New York City, NY, USA. (Dec. 17, 2009) pp. 3154–3159.Google Scholar
31. Song, D., Yi, J. and Goodwin, Z., “Localization of Unknown Networked Radio Sources Using a Mobile Robot with a Directional Antenna,” American Control Conference, 2007 (ACC '07) (Sep. 13, 2007) pp. 5952–5957.Google Scholar
32. Sun, Y., Xiao, J., Li, X. and Cabrera-Mora, F., “Adaptive Source Localization by a Mobile Robot Using Signal Power Gradient in Sensor Networks,” Global Telecommunications Conference, 2008, New Orleans, LA, USA. (Nov. 2008) pp. 1–5.Google Scholar
33. Vergassola, M., Villermaux, E. and Shraiman, B. I., “Infotaxis as a strategy for searching without gradients,” Nature 445 (7126), 406–409 (2007).Google Scholar
34. Viswanathan, G., Raposo, E. and da Luz, M. “Levy flights and superdiffusion in the context of biological encounters and random searches,” Phys. Life Rev. 5 (3), 133–150 (2008).Google Scholar
35. Grasso, F. W, Consi, T. R., Mountain, D. C. and Atema, J., “Biomimetic robot lobster performs chemo-orientation in turbulence using a pair of spatially separated sensors: Progress and challenges,” Robot. Auton. Syst. 30 (1–2), 115–131 (2000).Google Scholar
36. Zhang, X., Sun, Y. and Xiao, J., “Radio Source Search Using Force Field Vectors Weighted by Received Signal Strength Gradients,” 2011 International Conference on Mechatronics and Automation (ICMA), Beijing, China (7–10 Aug. 2011) pp. 531–536.Google Scholar
37. Zhang, X., Sun, Y. and Xiao, J., “A novel radio source search algorithm using force field vectors and received signal strengths,” Int. J. Mechatronics Autom. 3 (1), 25–35 (2013).Google Scholar
38. Zhang, X., Sun, Y., Xiao, J. and Cabrera-Mora, F., “Theseus Gradient Guide: An Indoor Transmitter Searching Approach Using Received Signal Strength,” IEEE International Conference on Robotics and Automation, 2011, Shanghai, China (May 2011) pp. 2560–2565.Google Scholar