CSE 6362: Parallel Algorithms for Artificial Intelligence
Parallel AI References

Parallel Search

• [Supplemental] R. E. Korf, ``Depth-First Iterative-Deepening: An Optimal Admissible Tree Search'', Artificial Intelligence, 27, pages 97-109, 1985.
• [1-30] C. Powley and R. E. Korf, ``Single-Agent Parallel Window Search'', in IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(5), 1991.
• [2-4] V. Kumar and V. N. Rao, ``Scalable Parallel Formulations of Depth-First Search'', in Parallel Algorithms for Machine Intelligence and Vision, Kumar, Kanal and Gopalakrishan (eds.), Springer-Verlag, pages 1-41, 1990.
• [2-6] L. V. Kale and V. A. Saletore, ``Parallel State-Space Search for a First Solution with Consistent Linear Speedups'', in International Journal of Parallel Programming, 19(4), pages 251-293, 1990.
• [2-6*] S. Dutt and N. R. Mahapatra, ``Parallel A* Algorithms and their Performance on Hypercube Multiprocessors'', Proceedings of the 7th IEEE Parallel Processing Symposium, pages 797-803, 1993.
• [Optional*] S. Dutt and N. Mahapatra, ``Scalable Load Balancing Strategies for Parallel A* Algorithms'', Journal of Parallel and Distributed Computing, 22, pages 488-505, 1994.
• [Optional] N. Mahapatra and S. Dutt, ``New Anticipatory Load Balancing Strategies for Parallel A* Algorithms'', Proceedings of the DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 1995.
• [2-13*] D. J. Cook and R. C. Varnell, ``Maximizing the Benefits of Parallel Search Using Machine Learning'', submitted to AAAI, 1997.
• [2-13] P. C. Nelson, ``Parallel Heuristic Search Using Islands'', Proceedings of the Fourth Conference on Hypercubes, Concurrent Computers and Applications, pages 909-916, 1989.
• [2-18] C. Powley, C. Ferguson, and R. E. Korf, ``Depth-First Heuristic Search on a SIMD Machine'', Artificial Intelligence, volume 60, pages 199-242, 1993.
• [Optional] A. Mahanti and C. J. Daniels, ``A SIMD approach to parallel heuristic search'', Artificial Intelligence, volume 60, pages 243-282, 1993.
• [Optional] D. J. Cook and G. Lyons, ``Massively Parallel IDA* Search'', International Journal of Artificial Intelligence Tools, volume 2, number 2, pages 163-180, 1993.
• [2-20] G. Karypis and V. Kumar, ``Unstructured Tree Search on SIMD Parallel Computers'', in Supercomputing '92, pages 453-462, 1992.
• [2-20] S. Aluru and J. Gustafson, ``Subtle issues of SIMD tree search'', Parallel Computing: Trends and Applications - Proceedings of the International Conference ParCo 93, 1993.
• [Optional] A. Colbrook and C. Smythe, ``Efficient Implementations of Search Trees on Parallel Distributed Memory Architectures'', in IEEE Proceedings: Computers and Digital Techniques, 137:394-400, September, 1990.
• [Optional] W. Ertel, ``Random Competition: A Simple, but Efficient Method for Parallelizing Inference Systems'', in Proceedings of the First Workshop on Parallel Processing for Artificial Intelligence, 1991.
• [Optional] Agrawal, D.P. and Janakiram, V.K. and Mehrotra, R., "A randomized parallel branch and bound algorithm", Proceedings of International Conference on Parallel Processing, 1988.
• [2-25*] M. Evett, J. Hendler, A. Mahanti, and D. Nau, ``PRA*: Massively Parallel Heuristic Search'', Journal of Parallel and Distributed Computing, 25, pages 133-143, 1995.

Parallel Rule-Based Systems

• [Supplemental] A. Gupta, ``Parallel OPS5 on the Encore Multimax'', in Proceedings of the International Conference on Parallel Processing, 1988.
• [3-6] J. G. Schmolze and S. Goel, ``A Parallel Asynchronous Distributed Production System'', in Proceedings of the National Conference on Artificial Intelligence, 1990.
• [3-6] S. Kuo and D. Moldovan, ``Performance Comparison of Models for Multiple Rule Firing'', pages 42-47, 1992.
• [3-11] V. V. Dixit and D. I. Moldovan, ``The Allocation Problem in Parallel Production Systems'', in Journal of Parallel and Distributed Computing, 8, 1991.
• [Optional] D. P. Miranker, C.-M. Kuo, and J. C. Browne, ``Parallelizing Compilation of Rule-Based Programs'', in Proceedings of the 1990 International Conference on Parallel Processing, 1990.
• [Optional] S. Kuo and D. Moldovan, ``The State of the Art in Parallel Production Systems'', in Journal of Parallel and Distributed Computing, 15, 1992.
• [Optional] D. Neiman, ``An Implementation of Multiple Worlds for Parallel Rule-Firing Production Systems'', 1992.
• [Optional] H. Dewan, S. Stolfo, and L. Woodbury, ``Scalable Parallel and Distributed Expert Database Systems with Predictive Load Balancing'', Journal of Parallel and Distributed Computing, 22, pages 506-522, 1994.
• [Optional] E. Jackson, L. Prasad, and L. O. Hall, ``Parallel Expert Systems for Current Hypercube Architectures'', Technical Report ISL-2-92, Department of Computer Science and Engineering, University of South Florida, 1992.
• [Optional] A. Acharya, M. Tambe, and A. Gupta, ``Implementation of Production Systems on Message-Passing Computers'', in Journal of Parallel and Distributed Systems, 3(4), 1992.
• [Optional] F.-C. Cheng, H.-H. Chen, and J.-H. Perng, ``Parallel Execution on Production Systems'', in Proceedings of the 2nd IEEE Symposium on Parallel and distributed processing, 1990.
• [Optional] W. Harvey, D. Kalp, M. Tambe, D. McKeown, and A. Newell, ``The Effectiveness of Task-Level Parallelism for Production Systems'', in Journal of Parallel and Distributed Computing, 13, pages 395-411, 1991.
• [Optional] D. Neiman, ``Control Issues in Parallel Rule-Firing Production Systems'', in Proceedings of the National Conference on Artificial Intelligence, 1991.
• [Optional] A. Sabharwal, ``Asynchronous Production Systems'', in Knowledge-based Systems, 2(2), 117-128, June, 1989.
• [Optional] J. G. Schmolze and D. E. Neiman, ``Comparison of Three Algorithms for Ensuring Serializable Executions in Parallel Production Systems'', in Proceedings of the National Conference on Artificial Intelligence, 1992.
• [Optional] H. Dai, T. J. Anderson, and F. C. Monds, ``On the Implementation Issues of a Parallel Expert System,'' Information and Software Technology, 34:739-55, Nov 1992.

Parallel Game Playing Algorithms

• [3-27*] R. Feldmann, P. Mysliwietz, and B. Monien, ``Studying Overheads in Massively Parallel Min/Max-Tree Evaluation'', SPAA '94: Sixth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 94-103, 1994.
• [Optional] R. Feldmann, B. Monien, and P. Mysliwietz, ``Distributed Game Tree Search'', in Parallel Algorithms for Machine Intelligence and Vision, Kumar, Kanal, and Gopalakrishan (eds.), Spring-Verlag, 1990.
• [4-1] Cung, Van-Dat and Gotte, Lucien, ``A First Step Towards the Massively Parallel Game-Tree Search: A SIMD Approach'', in Parallel Processing for Artificial Intelligence 2, chapter 10, Elsevier Science B.V., pages 117-129, 1994.

Parallel Neural Networks

• [4-3] X. Zhang, M. McKenna, J. Mesirov and D. Waltz, ``The backpropagation algorithm on grid and hypercube architectures'', in Parallel Computing, 14, 1990.
• [4-8] T. Nordstrom and B. Svensson, ``Using and Designing Massively Parallel Computers for Artificial Neural Networks'', in Journal of Parallel and Distributed Computing, 14, 1992.
• [Optional] V. Kumar, S. Shekhar, and M. B. Amin, ``A Scalable Parallel Formulation of the Backpropagation Algorithm for Hypercubes and Related Architectures'', IEEE Transactions on Parallel and Distributed Systems, 5(10), pages 1073-1090, 1994.
• [Optional] K. A. Grajski, G. Chinn, C. Chen, C. Kuszmaul and S. Tomboulian, ``Neural Network Simulation on the MasPar MP-1 Massively Parallel Processor'', The International Neural Network Conference, 1990.
• [Optional] G. Chinn, K. A. Grajski, C. Chen, C. Kuszmaul and S. Tomboulian, ``Systolic Array Implementations of Neural Nets on the MasPar MP-1 Massively Parallel Processor'', International Joint Conference on Neural Networks, 1990.
• [Optional] V. C. Barbosa and P. M. V. Lima, ``On the Distributed Parallel Simulation of Hopfield's Neural Networks'', in Software: Practice and Experience, 10:967-983, October, 1990.
• [Optional] L.-C. Chu and B. W. Wah, ``Optimal Mapping of Neural-Network Learning on Message-Passing Multicomputers'', in Journal of Parallel and Distributed Computing, 14, 1992.

Parallel Genetic Algorithms

• [4-17] R. J. Collins and D. R. Jefferson, ``Selection in Massively Parallel Genetic Algorithms'', in Proceedings of the Fourth International Conference on Genetic Algorithms, 1991.
• [4-17] P. Spiessens and B. Manderick, ``A Massively Parallel Genetic Algorithm'', in Proceedings of the Fourth International Conference on Genetic Algorithms, 1991.
• [Optional] S. Baluja, ``Structure and Performance of Fine-Grain Parallelism in Genetic Search'', Proceedings of the Fifth International Conference on Genetic Algorithms, 1993.
• [Optional] J. P. Cohoon, W. N. Martin, and D. S. Richards, ``A Multi-Population Genetic Algorithm for Solving the K-Partition Problem on Hyper-Cubes'', in Proceedings of the Fourth International Conference on Genetic Algorithms, 1991.
• [Optional] P. S. deSouza and S. N. Talukdar, ``Genetic Algorithms in Asynchronous Teams'', in Proceedings of the Fourth International Conference on Genetic Algorithms, 1991.
• [Optional] P. Husbands and F. Mill, ``Simulated Co-Evolution as the Mechanism for Emergent Planning and Scheduling'', in Proceedings of the Fourth International Conference on Genetic Algorithms, 1991.
• [Optional] J. T. Ngo and J. Marks, ``Massively Parallel Genetic Algorithm for Physically Correct Articulated Figure Locomotion'', in Proceedings of the AAAI Symposium on Innovative Applications of Massive Parallelism, 1993.
• [Optional] S. W. Mahfoud, and D. E. Goldberg, ``Parallel Recombinative Annealing: A Genetic Algorithm,'' Parallel Computing, 21:1-28, Jan 1995.
• [Optional] Dorigo and Sirtori, ``Alecsys: a parallel laboratory for learning classifier systems,'' Proceedings of the 4th International Conference on Genetic Algorithms, 1991.
• [Optional] R.-J. Chen, R. Meyer, and J. Yackel, ``A Genetic Algorithm for Diversity Minimization and Its Parallel Implementation'', Proceedings of the Fiften International Conference on Genetic Algorithms, 1993.
• [Optional] V. S. Gordon and D. Whitley, ``Serial and Parallel Genetic Algorithms as Function Optimizers'', Proceedings of the Fiften International Conference on Genetic Algorithms, 1993.
• [Optional] T. Maruyama, T. Hirose, and A. Konagaya, ``A Fine-Grained Parallel Genetic Algorithm for Distributed Parallel Systems'', Proceedings of the Fiften International Conference on Genetic Algorithms, 1993.
• [Optional] L. D. Merkel and G. B. Lamont, ``Comparison of Parallel Messy Genetic Algorithm Data Distribution Strategies'', Proceedings of the Fiften International Conference on Genetic Algorithms, 1993.
• [Optional] R. Shonkwiler, ``Parallel Genetic Algorithms'' Proceedings of the Fiften International Conference on Genetic Algorithms, 1993.

Parallel Machine Learning

• [4-29] R. Kufrin, ``Decision Trees on Parallel Processors'', Proceedings of the IJCAI Workshop on Parallel Processing for Artificial Intellience, pages 87-95, 1995.

Parallel Planning

• [Optional] Y. Xiang, ``A probabilistic framework for cooperative multi-agent distributed interpretation and optimizatin of communication'', Artificial Intelligence, 87, pages 295-342, 1996.
• [Optional] Sukhan Lee and Kyusik Chung, ``A Parallel Architecture for AI Nonlinear Planning'', in Applications of Learning and Planning, N. G. Bourbakis (ed.), chapter 8, World Scientific, pages 183-203, 1991.
• [Optional] J. Barnden and K. Srinivas, ``"Overcoming rule-based rigidity and connectionist limitations through massively-parallel case-based reasoning'', in International Journal of Man-Machine Studies, pages 221-246, February, 1992.
• [Optional] G. Grobe, ``Actor Coordination in Parallel Planning'', in Proceedings of the First Workshop on Parallel Processing for Artificial Intelligence, 1991.
• [Optional] T. Nishiyama, O. Katai, T. Sawaragi, S. Iwai and T. Katayama, ``Multiagent Planning by Distributed Constraint Satisfaction'', in Proceedings of the First Workshop on Parallel Processing for Artificial Intelligence, 1991.

Parallel Natural Language

• [Optional] A. Nijholt, ``Parallel Approaches to Context-Free Language Parsing'', Chapter 2, Parallel Natural Language Processing (G. Adriaens and U. Hahn, eds.), pages 135-167, 1994.
• [Optional] H. S. Thompson, ``Parallel Parsers for Context-Free Grammars -- Two Actual Implementations Compared'', Chapter 3, Parallel Natural Language Processing (G. Adriaens and U. Hahn, eds.), pages 168-187, 1994.
• [Optional] S. Winz and J. Geller, ``Methods of Large Grammar Representation in Massively Parallel Parsing Systems'', in Proceedings of the AAAI Symposium on Innovative Applications of Massive Parallelism, 1993.
• [Optional] R. Grishman and M. Chitrao, ``Evaluation of a Parallel Chart Parser'', Proceedings for the 2nd Conference on Applied Natural Language Processing, pages 71-76, 1988.
• [Optional] H. Kitano, ``Massively Parallel AI and its Application to Natural Language Processing'', in Proceedings of the First Workshop on Parallel Processing for Artificial Intelligence, 1991.
• [Optional] N. Ward, ``A Parallel Approach to Syntax for Generation, Artificial Intelligence, 57, 1992.

Parallel Inference Systems

• [Optional] M. Evett, J. A. Hendler, and L. Spector, ``Parallel Knowledge Representation on the Connection Machine'', Journal of Parallel and Distributed Computing, 22, 168-184, 1994.
• [Optional] J. Hendler, ``Massively-Parallel Marker-Passing in Semantic Networks'', Proceedings of the First Workshop on Parallel Processing for Artificial Intelligence, 1991.
• [Optional] B. D'Ambrosio, T. Fountain and Z. Li. ``Parallelizing Probabilistic Inference - Some Early Explorations'', in Proceedings of the 8th Conference on Uncertainty in Artificial Intelligence. D. Dubois, M. Wellman, B. D'Ambrosio and P. Smets, eds. 1992, pages 59-66.

AI Applied to Parallel Processing

• [5-6] B. Baumgartner, D. J. Cook, and B. Shirazi, ``Genetic Solutions to the Load Balancing Problem'', Proceedings of the 1995 ICPP Workshop on Challenges for Parallel Processing, pages 72-78, 1995.
• [Optional] E. S. H. Hou, R. Hong, and N. Ansari, ``Efficient Multiprocessor Scheduling Based on Genetic Algorithms'', in Proceedings of the 16th Annual Conference of IEEE Industrial Electronics Society, 1990.
• [Optional] T. Muntean and E. G. Talbi, ``A Parallel Genetic Algorithm for Process-Processors Mapping'', in High Performance Computing II, 1991.

Books

• Kumar, Kanal and Gopalakrishan (eds.), Parallel Algorithms for Machine Intelligence and Vision, Springer-Verlag, 1990.

  This book contains a collection of papers describing parallel AI algorithms.

• D. I. Moldovan, ``Parallel Processing from Applications to Systems'', Morgan Kauffman Publishers, San Mateo, CA, 1993.

  This book focus mostly on parallel computing techniques and types of parallel hardware, but does include a chapter on parallel rule-based systems and parallel natural language processing.

• M. Reeve and S. E. Zenith (eds.), ``Parallel Processing and Artificial Intelligence'', Wiley, 1989.

  This book focuses mostly on parallel inference systems and theorem-proving systems. A description is provided of parallel Prolog and Linda.

• G. Adriaens and U. Hahn (eds.), ``Parallel Natural Language Processing'', Ablex, 1994.

  This is a collection of papers on parallel NLP.

• IJCAI Workshop on Parallel Processing for AI, 1991.
• AAAI Symposium on Innovative Applications of Massive Parallelism, 1993.
• Parallel Processing for Artificial Intelligence, James Geller (ed.), North Holland / Elsevier Science, 1997.

  This book contains a collection of papers describing parallel AI algorithms.

• Third International Workshop on Parallel Processing for Artificial Intelligence, 1995.
• Artificial Intelligence.
• Journal of Parallel and Distributed Processing.

Class Presentations

2-27

3-25

3-25

3-27

4-10

4-10

4-22

4-24

4-24

• About this document ...