Abstract
A pervasive computing environment consists typically of a large heterogeneous collection of networked devices which can acquire and reason on context information. Embedded devices are used extensively in pervasive environments but they face some key challenges. Common path searching algorithms like A* Search can have exponential number of node expansions. In this paper, we describe a special variant of this problem called Multiple Objective Path Search (MOPS) and propose a memory bounded solution to implement it in a pervasive environment. Experimental results show that an efficient path with 40-60 times less node expansions can be obtained with the proposed solution.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Weiser, M.: The Computer for the 21st Century. Scientific American (1992)
Hopper. A.: Sentient Computing: The Royal Society Clifford Paterson Lecture. AT&T Laboratories Cambridge, Technical Report (1999)
Nelson, G.: Context-Aware and Location Systems: PhD Thesis. Cambridge University Computer Lab, UK (1998)
Markatos, E.P., Dramitinos, G.: Implementation of a Reliable Memory Pager. In: Proc. USENIX Tech. Conf., San Diego, California (1996)
Boling, D.: Minimizing the Memory Footprint of Your Windows CE based Program (1998), http://www.microsoft.com/msj/0598/memory.htm
Sathiaseelan, A., Radzik, T.: Using Remote Memory Paging for Handheld Devices in a Pervasive Computing Environment. King’s College London
Khuller, S., Malekian, A., Mestre, J.: To Fill or not to Fill: The Gas Station Problem. In: European Symp. on Algorithms (ESA), Spain (2007)
Teoh, E.J., Tang, H.J., Tan, K.C.: A Columnar Competitive Model with Simulated Annealing for Solving Combinatorial Optimization Problems. International Joint Conference on Neural Networks (2006)
Tang, H.J., Tan, K.C., Yi, Z.: A Columnar Competitive Model for Solving Combinatorial Optimization Problems. IEEE Transactions on Neural Networks 15, 1568–1574 (2004)
Jin, F.J., Wang, L.: A Distributed Multiobjective Optimal Algorithm based on MAS. In: Proceedings of the First International Conference on Innovative Computing, Information and Control (2006)
Roman, M., Campbell, R.H.: Gaia: Enabling Active Spaces. In: Proceedings of the 9th ACM SIGOPS European Workshop, Kolding, Denmark (2000)
Tao, Y., Papdias, D., Shen, Q.: Continuous Nearest Neighbor Search. In: Proc. 28th Very Large Data Bases Conference (2002)
Russell, S., Norvig, N.: Artificial Intelligence: A Modern Approach. Prentice Hall, Englewood Cliffs (1995)
Russell, S.: Efficient Memory-Bounded Search Methods. In: Proc. 10th European Conf. On Artificial Intelligence, pp. 1–5. Wiley, Chichester
Sheth, A., Ramakrishnan, C.: Semantic (Web) Technolog In Action: Ontology Driven Information Systems for Search, Integration and Analysis. In: IEEE Data Engineering Bulletin, Special issue on Making the Semantic Web Real (2003)
Kindberg, T., et al.: People, Places, Things: Web Presence for the Real World. In: Proceedings of the third WMCSA (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sundar, A.R., Tan, C.KY. (2008). Distributed Memory Bounded Path Search Algorithms for Pervasive Computing Environments. In: Ho, TB., Zhou, ZH. (eds) PRICAI 2008: Trends in Artificial Intelligence. PRICAI 2008. Lecture Notes in Computer Science(), vol 5351. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89197-0_37
Download citation
DOI: https://doi.org/10.1007/978-3-540-89197-0_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89196-3
Online ISBN: 978-3-540-89197-0
eBook Packages: Computer ScienceComputer Science (R0)