Decentralized vehicle routing in a stochastic and dynamic environment with customer impatience

ABSTRACT

Consider the following scenario: a spatio-temporal stochastic process generates service requests, localized at points in a bounded region on the plane; these service requests are fulfilled when one of a team of mobile agents visits the location of the request. For example, a service request may represent the detection of an event in a sensor network application, which needs to be investigated on site. Once a service request has been generated, it remains active for an amount of time which is itself a random variable, and then expires. The problem we investigate is the following: what is the minimum number of mobile agents needed to ensure that each service request is fulfilled before expiring, with probability at least 1 − ε? What strategy should they use to ensure this objective is attained? Formulating the probability of successfully servicing requests before expiration as a performance metric, we derive bounds on the minimum number of agents required to ensure a given performance level, and present decentralized motion coordination algorithms that approximate the optimal strategy.

REFERENCES

• 1: C.-F. Huang and Y.-C. Tseng. The coverage problem in a wireless sensor network. In 2nd ACM International Conference on Wireless Sensor Networks and Applications (WSNA), pages 115--121, New York, NY, USA, 2003. ACM Press.
• 2: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In 20th Annual IEEE Conference on Computer Communications (INFOCOM), pages 1380--1387, 2001.
• 3: X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C. Gill. Integrated coverage and connectivity configuration in wireless sensor networks. In SenSys '03: Proceedings of the 2nd international conference on Embedded networked sensor systems, pages 28--39, New York, NY, USA, 2003. ACM Press.
• 4: G. Xing, C. Lu, R. Pless, and J. A. O'Sullivan. Co-grid: an efficient coverage maintenance protocol for distributed sensor networks. In 3rd International Symposium on Information Processing in Sensor Networks (IPSN), pages 414--423, New York, NY, USA, 2004. ACM Press.
• 5: V. Isler. Placement and distributed deployment of sensor teams for triangulation based localization. In Proc. IEEE Int. Conf. on Robotics and Automation, 2006. to appear.
• 6: J. Cortés, S. Martínez, T. Karatas, and F. Bullo. Coverage control for mobile sensing networks. IEEE Transactions On Robotics and Automation, 20(2):243--255, 2004.
• 7: A. Howard, M. J. Mataric, and G. S. Sukhatme. Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem. In International Symposium on Distributed Autonomous Robotic Systems (DARS'04), pages 299--308, June 2002.
• 8: Y. Zou and K. Chakrabarty. Sensor deployment and target localization based on virtual forces. In 22nd Annual IEEE Conference on Computer Communications (INFOCOM), pages 1293--1303, 2003.
• 9: G. Wang, G. Cao, and T. La Porta. Movement-assisted sensor deployment. In 23rd Annual IEEE Conference on Computer Communications (INFOCOM), pages 2469--2479, 2004.
• 10: B. Liu, P. Brass, O. Dousse, Ph. Nain, and D. Towsley. Mobility improves coverage of sensor networks. In International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pages 300--308, New York, NY, USA, 2005. ACM Press.
• 11: E. Frazzoli and F. Bullo. Decentralized algorithms for vehicle routing in a stochastic time-varying environment. In Proc. IEEE Conf. on Decision and Control, Paradise Island, Bahamas, December 2004.
• 12: E. Frazzoli M. Pavone and F. Bullo. Decentralized algorithms for stochastic and dynamic vehicle routing with general target distribution. In IEEE Conference on Decision and Control, New Orleans, LA, 2007. To appear.
• 13: A. Arsie and E. Frazzoli. Efficient routing of multiple vehicles with no communications. International Journal of Robust and Nonlinear Control, 2007. To appear.
• 14: N. Bisnik, A. Abouzeid, and V. Isler. Stochastic event capture using mobile sensors subject to a quality metric. IEEE Tran. on Robotics, 2007. to appear.
• 15: W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider. Coordinated multi-robot exploration. IEEE Transactions on Robotics, 21(3):376--386, June 2005.
• 16: H. Choset. Coverage for robotics --- A survey of recent results. Annals of Mathematical and Artificial Intelligence, 31(1--4):113--126, 2001.
• 17: D. Kurabayashi, J. Ota, T. Arai, and E. Yoshida. Cooperative sweeping by multiple mobile robots. In IEEE International Conference on Robotics and Automation (ICRA), pages 1744--1749, 1996.
• 18: Y. Mei, Y.-H. Lu, Y. C. Hu, and C. S. George Lee. Deployment of mobile robots with energy and timing constraints. IEEE Transactions on Robotics, 22(3):507--522, June 2006.
• 19: J. Beardwood, J. Halton, and J. Hammersley. The shortest path through many points. Proceedings of the Cambridge Philoshopy Society, 55:299--327, 1959.
• 20: G. Percus and O. C. Martin. Finite size and dimensional dependence of the Euclidean traveling salesman problem. Physical Review Letters, 76(8):1188--1191, 1996.
• 21: R. C. Larson and A. R. Odoni. Urban Operations Research. Prentice-Hall, Englewood Cliffs, NJ, 1981.
• 22: F. Aurenhammer. Voronoi diagrams: a survey of a fundamental geometric data structure. ACM Computing Surveys, 23(3):345--405, 1991.
• 23: S. Fortune. Voronoi diagrams and Delaunay triangulations. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 20, pages 733--754. CRC Press, Boca Raton, FL, 1997.
• 24: B. Boots A. Okabe and K. Sugihara. Nearest neighbourhood operations with generalized Voronoi diagrams: a review. International Journal of Geographical Information Systems, 8(1):43--71, 1994.
• 25: R. Klein. Concrete and abstract Voronoi diagrams. In Lecture Notes in Computer Science, volume 400. Springer Verlag, New York, NY, 1989.
• 26: D. J. Bertsimas and G. J. van Ryzin. A stochastic and dynamic vehicle routing problem in the Euclidean plane. Operations Research, 39:601--615, 1991.
• 27: D. J. Bertsimas and G. J. van Ryzin. Stochastic and dynamic vehicle routing with general demand and interarrival time distributions. Operations Research, 41(1):60--76, 1993.
• 28: D. J. Bertsimas and G. J. van Ryzin. Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles. Advances in Applied Probability, 25(4):947--978, 1993.
• 29: K. Sugihara A. Okabe, B. Boots and S. N. Chiu. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, New York, NY, 2000.
• 30: R. G. Gallager. Discrete Stochastic Processes. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996.

INDEX TERMS

Keywords:
mobile robotic networks, sensor networks, traveling salesman problem