Search

In this paper, we introduce an effective strategy for subgoal division and ordering based upon recursive subgoals and combine this strategy with a genetic-based planning approach. This strategy can be applied to domains with conjunctive goals. The main idea is to recursively decompose a goal into a set of serializable subgoals and to specify a strict ordering among the subgoals. Empirical results show that the recursive subgoal strategy reduces the size of the search space and improves the quality of solutions to planning problems., {"references":["Tower of Hanoi, http://www.cut-the-knot.com/recurrence/hanoi.shtml.","A. Barrett and D. S. Weld. \"Characterizing subgoal interactions for\nplanning.\" In Proc. of the 13th International Joint Conference on\nArtificial Intelligence (IJCAI-93), pages 1388-1393, Chambery, France,\n1993.","A. Barrett and D. S. Weld. \"Partial-order planning: evaluating possible\nefficiency gains.\" Journal of Artificial Intelligence, 67:71-112, 1994.","J. Cheng and K. B. Irani. \"Ordering problem subgoals.\" In Proc. of the\n11th International Joint Conference on Artificial Intelligence (IJCAI-\n89), pages 931-936, Detroit, USA, 1989.","M. Drummond and K. Currie. \"Goal ordering in partially ordered plans.\"\nIn Proc. of the 11th International Joint Conference on Artificial\nIntelligence (IJCAI-89), pages 960-965, Detroit, USA, 1989.","O. Etzioni. \"Acquiring search-control knowledge via static analysis.\"\nJournal of Artificial Intelligence, 62:255-301,1993.","R. Fikes and N. Nilsson. \"STRIPS: A new approach to the application of\ntheorem proving to problem solving.\" Journal of Artificial Intelligence,\n2(3/4):189-208, 1971.","J. Hertzberg and A. Horz. \"Towards a theory of conflict detection and\nresolution in nonlinear plans.\" In Proc. of the 11th International Joint\nConference on Artificial Intelligence (IJCAI-89), pages 937-942,\nDetroit, USA, 1989.","W. W. Johnson and W. E. Story. \"Notes on the ÔÇÿ15- puzzle.\" American\nJournal of Mathematics, 2(4):397-404, 1879.\n[10] J. Koehler and J. Hoffmann. \"Planning with goal agendas.\" Technical\nReport 110, Institute for Computer Science, Albert Ludwigs University,\nFreiburg, Germany, 1998.\n[11] R. E. Korf. \"Planning as search: A quantitative approach.\" Journal of\nArtificial Intelligence, 33:65-88, 1987.\n[12] R. E. Korf, personal communication, 2003.\n[13] R. E. Korf and A. Felner. \"Disjoint pattern database heuristics.\" Journal\nof Artificial Intelligence, 134:9-22, 2002.\n[14] R. E. Korf and L. A. Taylor. \"Finding optimal solutions to the twentyfour\npuzzle.\" In Proc. of the Thirteenth National Conference on\nArtificial Intelligence (AAAI 96), pages 1202-1207, Portland, OR,\n1996.\n[15] F. Lin. \"An ordering on subgoals for planning.\" Annals of Mathematics\nand Artificial Intelligence, 21(2-4):321-342, 1997.\n[16] S. J. Russell and P. Norvig. \"Artificial Intelligence: A Modern\nApproach.\" Prentice Hall, Upper Saddle River, NJ, 1995.\n[17] H. Yu, D. C. Marinescu, A. S.Wu, and H. J. Siegel. \"A genetic approach\nto planning in heterogeneous computing environments.\" In the 12th\nHeterogeneous Computing Workshop (HCW 2003), CD-ROM Proc. of\nthe 17th International Parallel and Distributed Processing Symposium\n(IPDPS 2003). IEEE Computer Society Press, Los Alamitos, CA, ISBN\n0-7695-1926-1, 2003."]}

We discuss the application of matching in the area of resource discovery and resource allocation in grid computing. We present a formal definition of matchmaking, overview algorithms to evaluate different matchmaking expressions, and develop a matchmaking service for an intelligent grid environment., {"references":["1] X. Bai, H. Yu, Y. Ji, and D. C. Marinescu. ''Evaluation of a matchmaking service for a grid environment.'' The Fourteenth International Heterogeneous Computing Workshop, Denver, Colorado,April 4, 2005(submitted).","N. Singh. \"A common Lisp API and facilitator for ABSI: version 2.0.3.\" Technical Report Logic-93-4, Logic Group, Computer Science Department, Stanford University, 1993.","D. Kuokka and L. Harada. ''Matchmaking for information agents.''Proceedings of 14th IJCAI, 672-678, 1995.","R. J. Bayardo Jr., W. Bohrer, R. Brice, A. Cichocki, J. Fowler, A. Helal, V. Kashyap, T. Ksiezyk, G. Martin, M. Nodine, M. Rashid, M. Rusinkiewicz, R. Shea, C. Unnikrishnan, A. Unruh, and D. Woelk.''Info Sleuth: agent-based semantic integration of information in open and dynamic environments.'' Reading in Agents, Morgan Kaufmann,CA, 205-216, 1998.","V. S. Subrahmanian, J. Dix, and F. Ozcan. ''Heterogeneous agent systems.'' The MIT Press, 2000.","G. J. Wickler. ''Using expressive and flexible action representations to reason about capabilities for intelligent agent cooperation.'' PhD thesis,University of Edinburgh, 1999.","K. Sycara, S. Wido, M. Klusch, and J. Lu. ''LARKS: dynamic matchmaking among heterogeneous software agents in cyberspace.''Autonomous Agents and Multi-Agent Systems, 5, 173-203, 2002.","K. Sycara, J. Lu, and M. Klusch. ''Interoperability among heterogeneous software agents on the Internet.'' Carnegie Mellon University, PA, Technical Report CMU-RI-TR-98-22.","M. Paolucci, N. Srinivasan, K. Sycara, and T. Nishimura. \"Towards a semantic choreography of Web services: From WSDL to DAML-S.\"Proceedings of ICWS'03. [10] R. Raman, M. Livny, and M. Solomon. ''Matchmaking: distributed resource management for high throughput computing.'' In Proceedings of the Seventh IEEE International Symposium on High Performance Distributed Computing, July 1998.[11] S. Nestorov, A. Abiteboul, and R. Motwani. \"Inferring structure in semistructured data.\" In Proceedings of the Workshop on Management of Semistructured Data, Rucson, Arizona, May 1997.[12] C. Liu, L. Yang, I. Foster, and D. Angulo. ''Design and evaluation of a resource selection framework for grid applications.'' In Proceedings of the 11th IEEE Symposium on High-Performance Distributed Computing, 2002.[13] Z. Zhang and C. Zhang. ''An improvement to matchmaking algorithms for middle agent.'' AAMAS, Bologna, Italy, 2002.[14] http://protege.stanford.edu/[15] X. Bai, H. Yu, G. Wang, Y. Ji, D. C. Marinescu, G. M. Marinescu, and L. Bölöni. ''Intelligent grids.'', ''Grid computing: software environments and tools'', Jose C. Cunha and O.F. Rana Eds, Springer Verlag,Heidelberg, 2004 (in print)."]}