A Logic Based Framework for Planning for Mobile Agents

Authors: Rajdeep Niyogi

Abstract:

The objective of the paper is twofold. First, to develop a formal framework for planning for mobile agents. A logical language based on a temporal logic is proposed that can express a type of tasks which often arise in network management. Second, to design a planning algorithm for such tasks. The aim of this paper is to study the importance of finding plans for mobile agents. Although there has been a lot of research in mobile agents, not much work has been done to incorporate planning ideas for such agents. This paper makes an attempt in this direction. A theoretical study of finding plans for mobile agents is undertaken. A planning algorithm (based on the paradigm of mobile computing) is proposed and its space, time, and communication complexity is analyzed. The algorithm is illustrated by working out an example in detail.

Keywords: Acting, computer network, mobile agent, mobile computing, planning, temporal logic.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062424

References:

[1] F. Bacchus and F. Kabanza. Planning for temporally extended goals. Annals of Mathematics and Artifi cial Intelligence, 22:5-27, 1998.
[2] C. Baral, V. Kreinovich, and R. Trejo. Computational complexity of planning with temporal goals. In Proceedings of IJCAI, pages 509-514, 2001.
[3] M. Beetz and D. McDermott. Improving robot plans during their execution. In Proceedings of AIPS, 1994.
[4] P. Bellavista, A. Corradi, C. Federici, R. Montanari, and D. Tibaldi. Security for mobile agents: issues and challenges. Handbook of mobile computing: I. Mahgoub and M. Ilyass (eds), 2004.
[5] A. Bieszczad, B. Pagurek, and T. White. Mobile agents for network management. IEEE Communications Surveys, 1998.
[6] A. Blum and L. Furst. Fast planning through planning graph analysis. Artifi cial Intelligence, 90:281-300, 1997.
[7] L. Cardelli. Wide area computation. In Proceedings of ICALP, LNCS 1644, pages 10-24, 1999.
[8] E.M. Clarke, E.A. Emerson, and A.P. Sistla. Automatic verifi cation of fi nite-state concurrent systems using temporal logic specifi cations. ACM Transactions of Programming Languages and Systems, 8(2):244-263, 1986.
[9] J.E. Cook. Software engineering concerns for mobile agent systems. In Proceedings of the Workshop on Software Engineering and Mobility, 2001.
[10] A. Fuggetta, G. Picco, and G. Vigna. Understanding code mobility. IEEE Transactions on Software Engineering, 24(5):342-361, 1998.
[11] M. Ghallab, D. Nau, and P. Traverso. Automated Planning: Theory and Practice. Morgan Kaufmann Publishers, 2004.
[12] F. Giunchiglia and P. Traverso. Planning as model checking. In Proceedings of European Conference on Planning, pages 1-20, 1999.
[13] J. Hoffmann and B. Nebel. The ff planning system: Fast plan generation through heuristic search. Artifi cial Intelligence, 14:253-302, 2001.
[14] D. Kotz and R. Gray. Mobile agents and the future of the internet. ACM Operating Systems Review, 33(2):7-13, 1999.
[15] H. Levesque. What is planning in the presence of sensing? In Proceedings of AAAI, 1996.
[16] K. Moizumi. Mobile agents planning problem. In PhD thesis, Dartmouth College, 1998.
[17] A. Murphy and G. Picco. Reliable communication for highly mobile agents. Journal of Autonomous Agents and Multi-Agent Systems, 5(1):81-100, 2002.
[18] C.H. Papadimitriou and M. Yannakakis. Shortest paths without a map. Theoretical Computer Science, 84:127-150, 1991.
[19] M. Pistore and P. Traverso. Planning as model checking for extended goals in non-deterministic domains. In Proceedings of IJCAI, pages 479-486, 2001.
[20] P. Rodriguez, C. Spanner, and E.W. Biersack. Analysis of web caching architectures: hierarchical and distributed caching. IEEE Transactions on networking, 9(4):404-418, 2001.
[21] J.A. Sauter, R. Matthews, H. van dyke Parunak, and S. Brueckner. Evolving adaptive pheromone path planning mechanisms. In Proceedings of AAMAS, 2002.
[22] M. Sharma, S. Iyengar, and N. Mandyam. An effi cient distributed depth fi rst search algorithm. Information Processing Letters, 32:183- 186, 1989.
[23] L. Spalazzi and P. Traverso. A dynamic logic for acting, sensing, and planning. Logic Computation, 10(6):727-821, 2000.
[24] S. Thiebaux and M. Cordier. Supply restoration in power distribution systems-a benchmark for planning under uncertainty. In Proceedings of ECP, 2001.
[25] P. Wojciechowski. Algorithms for location-independent communication between mobile agents. In Proceedings of AISB -01 Symposium on Software Mobility and Adaptive Behaviour, 2001.