An event-driven algorithm for agents on the web. (English) Zbl 1171.68309
Jain, Lakhmi C. (ed.) et al., Knowledge processing and decision making in agent-based systems. Berlin: Springer (ISBN 978-3-540-88048-6/hbk; 978-3-540-88049-3/ebook). Studies in Computational Intelligence 170, 147-174 (2009).
Summary: This chapter describes how meta-agents in a multi-agent system can be used to effectively search for services in networks with an event-driven algorithm. These services can be attained in a range of different ways, including a simultaneous combination of several services in order to optimize costs and time. A challenge with a network is finding and extracting an optimal combination of the different services to implement a complex requested service. To solve this problem, it is possible to develop multi-agent systems in which the task steers the agents. While finding information on the web, the search path becomes an event-driven algorithm. The algorithm acts as a search method to extract information from several different services. Once built up, the algorithm can guide future search and optimize the searching.
For the entire collection see [Zbl 1159.68002].
For the entire collection see [Zbl 1159.68002].
MSC:
| 68M10 | Network design and communication in computer systems |
| 68P10 | Searching and sorting |
| 68W05 | Nonnumerical algorithms |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Apelkrans, M., Håkansson, A.: Information coordination using Meta-Agents in Information Logistics Processes. In: 12th International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, KES 2008, September 3-5, Zagreb, Croatia (2008) |
| [2] | Akl, S. G.; Bernard, D. T.; Jordan, R. J., Design and implementation of a parallel tree search algorithm, IEEE transactions on Pattern Analysis and Machine Intelligence, PAMI-4, 192-203 (1982) · Zbl 0476.68049 · doi:10.1109/TPAMI.1982.4767226 |
| [3] | Baudet, G.M.: The Design and Analysis of Algorithms for Asynchronous Multiprocessors. Ph D Thesis, Carnegie-Mellon University, Pittsburgh, PA (1978) · Zbl 0372.68015 |
| [4] | Bentley, J. L., A parallel algorithm for constructing minimum spanning trees, Journal of the ACM, 27, 1, 51-59 (1980) · Zbl 0435.68049 |
| [5] | Berman, K., Paul, J.: Algorithms: Sequential, Parallel, and Distributed. Course Technology, 1st edn. (2004) |
| [6] | Brungger, A.; Marzetta, J.; Clausen, J.; Perregaard, M., Solving large-scale QAP problems in parallel with the search library zram, Journal of Parallel and Distributed Computing, 50, 157-169 (1998) · Zbl 0909.68171 · doi:10.1006/jpdc.1998.1434 |
| [7] | Chakrabarti, S.; van den Berg, M.; Dom, B., Focused crawling: A new approach to topic-specific web resource discovery, Computer Networks, 31, 11-16, 1623-1640 (1999) · doi:10.1016/S1389-1286(99)00052-3 |
| [8] | Chelberg, D., Welch, L., Lakshmikumar, A., Gillen, M., Zhou, Q.: Meta-Reasoning For a Distributed Agent Architecture. In: System Theory, Proceedings of the 33rd Southeastern Symposium, pp. 377-381 (2001) |
| [9] | Cheong, F.-C.: Internet Agents: Spiders, Wanderers, Brokers, and Bots. New Riders Pub., Indianapolis (1996) |
| [10] | Cormen, T. H.; Leiserson, C. E.; Riverst, R. L.; Stein, C., Introduction to Algorithms (2006), Cambridge: MIT Press, Cambridge |
| [11] | Costantini, S.; Kakas, A.; Sadri, F., Meta-reasoning: a survey, Computational Logic: From Logic Programming into the Future: Special volume in honour of Bob Kowalski (in print) (2002), Berlin: Springer, Berlin · Zbl 0997.00044 |
| [12] | Crowder, H.; Johnson, E. L.; Padberg, M., Solving large-scale zero-one linear programming problem, Operations Research, 2, 803-834 (1983) · Zbl 0576.90065 · doi:10.1287/opre.31.5.803 |
| [13] | Dijkstra, E. W., A note on two problems in connexion with graphs, Numerische Mathematik, 1, 269-271 (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390 |
| [14] | Dunkels, A., Schmidt, O., Voigt, T., Ali, M.: Protothreads: simplifying event-driven programming of memory-constrained embedded systems. In: Proceedings of the Fourth ACM Conference on Embedded Networked Sensor Systems, Boulder, Colorado, USA (2006) |
| [15] | Ferg, S.: Event-Driven Programming: Introduction, Tutorial, History (2006-02-08), http://TutorialEventDrivenProgramming.sourceforge.net |
| [16] | Finkel, R. A.; Fishburn, J. P., Parallelism in alpha-beta search, Artificial Intelligence, 19, 89-106 (1982) · Zbl 0491.68091 · doi:10.1016/0004-3702(82)90022-4 |
| [17] | Gendron, B., Crainic, T.G.: Parallel Branch-And-Bound Algorithms: Survey and Synthesis Operations Research 42(6), 1042-1066 (1994) · Zbl 0824.90096 |
| [18] | Genesereth, M. R.; Ketchpel, S. P., Software Agents, Communication of the ACM, 37, 7, 18-21 (1994) · doi:10.1145/176789.176794 |
| [19] | Gibbons, A., Algorithmic graph theory (1985), Cambridge: Cambridge University Press, Cambridge · Zbl 0568.05001 |
| [20] | Grama, A.; Gupta, A.; Karypis, G.; Vipin, K., Introduction to Parallel Computation (2003), Reading: Pearon Addison Wesley, Reading |
| [21] | Hermans, B.: Intelligent Software Agents on the Internet, Ch. 1-3. First Monday 2(3) (1997) |
| [22] | Horowitz, E., Sahni, S., Rajasekaran, S.: Computer Algorithms C++: C++ and Pseudo code Versions, 2nd Rev. edn., December 15, p. 769. W. H. Freeman (1996) |
| [23] | Håkansson, A., Hartung, R.: Using Meta-Agents for Multi-Agents in Networks. In: Proceedings of the 2007 International Conference on Artificial Intelligence, ICAI 2007, vol. II, pp. 561-567. CSREA Press (2007) |
| [24] | Håkansson, A.; Hartung, R., Calculating optimal decision using Meta-level agents for Multi-Agents in Networks, Proceedings of Knowledge-Based and Intelligent Information & Engineering Systems, 11th International Conference, 180-188 (2007), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-74819-9_23 |
| [25] | Håkansson, A., Hartung, R.: Autonomously creating a hierarchy of intelligent agents using clustering in a multi-agent system. In: The 2008 International Conference on Artificial Intelligence, ICAI 2008, Las Vegas, Nevada, USA, July 14-17 (submitted, 2008) |
| [26] | Håkansson, A.; Hartung, R. L.; Nguyen, N. T.; Jo, G. S.; Howlett, R. J.; Jain, L. C., An approach to event-driven algorithm for intelligent agents in multi-agent systems, Agent and Multi-Agent Systems: Technologies and Applications, 411-420 (2008), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-78582-8_42 |
| [27] | Ishida, T., Real-Time Search for Autonomous Agents and Multi-Agent Systems, Journal of Autonomous Agents and Multi-Agent Systems, 1, 2, 139-167 (1998) · doi:10.1023/A:1026449201026 |
| [28] | Jade, Java Agent Development Framework (2008-03-15), http://jade.tilab.com/ |
| [29] | Kanal, L. N.; Kumar, V., Search in Artificial Intelligence (1988), New York: Springer, New York · Zbl 0648.68104 |
| [30] | Kleinberg, J., Authoritative sources in a hyperlinked environment, Proc. Ninth Ann. ACM-SIAM Symp. Discrete Algorithms, 668-677 (1998), New York: ACM Press, New York · Zbl 0930.68047 |
| [31] | Kruskal, J. B., On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proceedings of the American Mathematical Society, 7, 1, 48-50 (1956) · Zbl 0070.18404 · doi:10.2307/2033241 |
| [32] | Kumar, V.; Rao, V. N., Parallel depth-first search, part II: Analysis, International Journal of Parallel Programming, 16, 6, 501-519 (1987) · Zbl 0665.68049 · doi:10.1007/BF01389001 |
| [33] | Kumar, V.; Singh, V., Scalability of parallel algorithms for the all-pairs shortest path problem, Journal of Parallel and Distributed Computing, 13, 2, 124-128 (1991) · doi:10.1016/0743-7315(91)90083-L |
| [34] | Kumar, V., Ramesh, K., Rao, V.N.: Parallel best-first search of state-space graphs: A summary of results. In: Processings of the 1988 National Conference on Artificial Intelligence, pp. 122-126 (1988) |
| [35] | Luger, G. F., Artificial Intelligence - Structures and strategies for Complex Problem Solving (2002), London: Pearson Education, London |
| [36] | Maes, P.; Guttman, R. H.; Moukas, A. G., Agents that buy and sell, Communications of the ACM archive, 42, 3, 81-92 (1999) · doi:10.1145/295685.295716 |
| [37] | Menczer, F.: ARACHNID: Adaptive Retrieval Agents Choosing Heuristic Neighbourhoods for Information Discovery. In: Fisher, D. (ed.) Proceedings of the 14th International Conference on Machine Learning, ICML 1997 (1997) |
| [38] | Menczer, F.; Pant, G.; Srinivasan, P., Topical Web Crawlers: Evaluating Adaptive Algorithms, ACM transactions on Internet Technology (TOIT), 4, 4, 378-419 (2004) · doi:10.1145/1031114.1031117 |
| [39] | Miller, D.L., Pekny, J.F.: The role of performance metrics for parallel mathematical programming algorithms. ORSA Journal on Computing 5(1) (1993) |
| [40] | Mohan, J.: Experience with two parallel programs solving the travelling salesman problem. In: Proceeding of the 1983 International Conference on Parallel Processing, pp. 191-193 (1983) |
| [41] | Mornien, B., Vornberger, O.: Parallel processing of combinatorial search trees. In: Proceedings of International Workshop on Parallel Algorithms and Architectures (1987) |
| [42] | Nisan, N.: Algorithms for Selfish Agents - Mechanism Design for Distributed Computation. In: Proceedings of Annual Symposium on Theoretical Aspects of Computer Science Trier, pp. 1-15 (1999) |
| [43] | Page, L.; Brin, S.; Motwani, R.; Winograd, T.: The PageRank Citation Ranking: Bringing Order to the Web (1999) (2008-03-09), http://dbpubs.stanford.edu/pub/1999-66 |
| [44] | Paige, R.C., Kruskal, C.P.: Parallel algorithms for shortest path problems. In: Proceedings of 1989 International Conference of Parallel Processing, pp. 14-19 (1989) |
| [45] | Pearl, J., Heuristics-Intelligent Search Strategies for Computer Problem Solving (1984), Reading: Addison-Wesley, Reading |
| [46] | Peng, C.-H.; Wang, B.-F.; Wang, J.-S., Recognizing unordered depth-first search of an undirected graph in parallel, IEEE Transactions on Parallel and Distributed Systems, 11, 6, 559-570 (2000) · doi:10.1109/71.862207 |
| [47] | Pfeifer, A., Ururahy, C., Rodriguez, N., Ierusalimschy, R.: Event-Driven Programming for Distributed Multimedia Applications. In: Distributed Computing Systems Workshops Proceedings. 22nd International Conference on Distributed Computing Systems, pp. 583-584 (2002) |
| [48] | Prim, R. C., Shortest connection networks and some generalizations, Bell System Technical Journal, 36, 1389-1401 (1957) |
| [49] | Rippel, E.; Bar-Gill, A.; Shimkin, N., Fast Graph-Search Algorithms for General-Aviation Flight Trajectory Generation, Journal of guidance control and dynamics, American inst of aeronautics and astronautics, 28, 4, 801-811 (2005) |
| [50] | Russell, S.; Norvig, P., Artificial Intelligence: A Modern Approach (1995), Englewood Cliffs: Prentice-Hall, Inc., Englewood Cliffs · Zbl 0835.68093 |
| [51] | Sedgewick, R.: Algorithms in Java, Part 5: Graph Algorithms, 3rd edn. Addison-Wesley Longman Publishing Co, Inc. (2003) |
| [52] | Skiena, S., The Algorithm Design Manual (1998), Heidelberg: Springer, Heidelberg · Zbl 1149.68081 |
| [53] | Sauer, J., Appelrath, H.-J.: Scheduling the Supply Chain by Teams of Agents. In: The 36th Annual Hawaii International Conference on System Sciences, 81 (2003) |
| [54] | Winston, P. H., Artificial Intelligence (1992), Reading: Addison-Wesley, Reading |
| [55] | Wooldridge, M., An Introduction to MultiAgent Systems (2002), Chichester: John Wiley & Sons Ltd, Chichester |
| [56] | Wooldridge, M., Jennings, N.R.: Intelligent agents: Theory and practice. Knowledge Engineering Review 10(2) (1995) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
