Abstract
We consider the problem of computing the maximum-reward motion in a reward field in an online setting. We assume that the robot has a limited perception range, and it discovers the reward field on the fly. We analyze the performance of a simple, practical lattice-based algorithm with respect to the perception range. Our main result is that, with very little perception range, the robot can collect as much reward as if it could see the whole reward field, under certain assumptions. Along the way, we establish novel connections between this class of problems and certain fundamental problems of nonequilibrium statistical mechanics . We demonstrate our results in simulation examples.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Ad-hoc sensor networks may also be very valuable for environmental monitoring. In fact, such technologies have been developed over past years. We note that the presented approach is for motivational purposes. Yet, it may be beneficial over the ad-hoc network approach due to substantial energy savings at the stationary sensors (as communication requirement is much lower); hence, the sensor nodes require less maintenance. The main drawbacks are additional complexity of a mobile vehicle, and communication delay due to the mobile vehicles physically carrying the data.
References
Heer, C.V.: Statistical Mechanics, Kinetic Theory, and Stochastic Processes. Academic Press, New York (2012)
Mazonko, G.F.: Nonequilibrium Statistical Mechanics. Wiley, Weinheim (2008)
Chou, T., Mallick, K., Zia, R.K.P.: Non-equilibrium statistical mechanics: from a paradigmatic model to biological transport. Rep. Prog. Phys. (2011)
Shaw, L.B., Zia, R.K.P., Lee, K.H.: Totally asymmetric exclusion process with extended objects: a model for protein synthesis. Phys. Rev. E 68(2), (021910) (2003)
Ingber, L.: Statistical mechanics of nonlinear nonequilibrium financial markets. Math. Model. 5, 343–361 (1984)
Antal, T., Schutz, G.M.: Asymmetric exclusion process with next-nearest-neighbor interaction: some comments on traffic flow and a nonequilibrium reentrance transition. Phys. Rev. E 62(1), 83–93 (2000)
Nagatani, T.: Bunching of cars in asymmetric exclusion models for freeway traffic. Phys. Rev. E 51(2), 922–928 (1995)
Fleming, G.R., Ratner, M.A.: Grand challenges in basic energy sciences. Phys. Today 61(7), 28 (2008)
Basic Energy Sciences Advisory Committee. Directing matter and energy: five challanges for science and imagination. pp. 1–144. November 2007
National Research Council Committee on CMMP 2010. Condensed-matter and materials physics: the science of world around us. January 2010
Otte, M., Correll, N., Frazzoli, E.: Navigation with foraging. In: 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3150–3157. IEEE (2013)
Karaman, S., Frazzoli, E.: High-speed flight in an ergodic forest. In: IEEE International Conference on Robotics and Automation (2011)
Antoine, B., Jean-Christophe, Z., Dario, F.: Vision-based control of near-obstacle flight. Auton. Robots 27(3), 201–219 (2009)
Scherer, S., Singh, S., Chamberlain, L., Elgersma, M.: Flying fast and low among obstacles: methodology and experiments. Int. J. Robot. Res. 27(5), 549–574 (2008)
Bertsimas, D.J.: A stochastic and dynamic vehicle routing problem in the Euclidean plane. Oper. Res. 39(4), 601–615 (2008)
Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities : A Nonasymptotic Theory of Independence. Oxford University Press, Oxford (2013)
Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York (2009)
Dumaz, L., Virág, B: The right tail exponent of the tracy-widom-beta distribution. arXiv preprint arXiv:1102.4818 (2011)
Johansson, K.: Shape fluctuations and random matrices. Commun. Math. Phys. 209(2), 437–476 (2000)
Martin, J.B.: Linear growth for greedy lattice animals. Stoch. Process. Appl. 98(1), 43–66 (2002)
Martin, J.B.: Last-passage percolation with general weight distribution. Markov Process. Relat. Fields 12(2), 273–299 (2006)
Zeng, X., Hou, Z., Guo, C., Guo, Y.: Directed last-passage percolation and random matrices. Adv. Math. 42(3), 3 (2013)
Urmson, C., et al.: Autonomous driving in urban environments: boss and the urban challenge. J. Field Robot. 25(8), 425–466 (2008)
Koenig, S., Likhachev, M., Furcy, D.: Lifelong planning A\(\ast \). Artif. Intel. (2004)
Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)
Steele, M.J.: Probability Theory and Combinatorial Optimization. SIAM, Philadelphia (1996)
Dumaz, L., Virág, B.: The right tail exponent of the Tracy-Widom \(\beta \) distribution. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 49(4), 915–933 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Ma, F., Karaman, S. (2015). Maximum-Reward Motion in a Stochastic Environment: The Nonequilibrium Statistical Mechanics Perspective. In: Akin, H., Amato, N., Isler, V., van der Stappen, A. (eds) Algorithmic Foundations of Robotics XI. Springer Tracts in Advanced Robotics, vol 107. Springer, Cham. https://doi.org/10.1007/978-3-319-16595-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-16595-0_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16594-3
Online ISBN: 978-3-319-16595-0
eBook Packages: EngineeringEngineering (R0)