Top

The Journal of Supercomputing

Published in:

24-05-2020

Parallelized path-based search for constraint satisfaction in autonomous cognitive agents

Authors: Tanvir Atahary, Tarek M. Taha, Scott Douglass

Published in: The Journal of Supercomputing | Issue 2/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Cognitive agents are typically utilized in autonomous systems for automated decision making. With the widespread use of autonomous systems in complex environments, the need for real-time cognitive agents is essential. Cognitive agents are more capable when they are able to process larger amounts of information to make more informed and intelligent decisions. The solution search space for cognitive agents increases exponentially with large volumes of varied data. In this paper, we present the parallelization of the knowledge-mining component of a cognitive agent that can be programmed to reason like humans. This study examined a novel high-performance path-based forward checking algorithm on 128 compute nodes at the Ohio Supercomputing Center (768 cores) to achieve a speedup of over 200 times compared to a serial implementation of our algorithm. The serial implementation is around 10–25 times faster than a conventional Java-based constraint solver at generating the first solution.

previous article ELS: Emulation system for debugging and tuning large-scale parallel programs on small clusters

next article A lightweight anonymous authentication scheme for secure cloud computing services

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Wray R, Chong R, Phillips J, Rogers S, Walsh B (1994) A survey of cognitive and agent architectures. Retrieved 28 Jan 2007 from http://ai.eecs.umich.edu/cogarch0/

Chong HQ, Tan AH, Ng GW (2007) Integrated cognitive architectures: a survey. Artif Intell Rev 28:103–130CrossRef

Laird JE (2012) The soar cognitive architecture. MIT Press, CambridgeCrossRef

Anderson JR (1983) The architecture of cognition. Harvard University Press, Harvard

Anderson JR (1997) How can the human mind exist in the physical universe?. Oxford University Press, Oxford

Anderson JR, Bothell D, Byrne MD, Douglass S, Lebiere C, Qin Y (2004) An integrated theory of the mind. Psychol Rev 111(4):1036–1060. https://doi.org/10.1037/0033-295X.111.4.1036CrossRef

Atahary T, Taha T, Douglass S (2016) Parallelized mining of domain knowledge on GPGPU and Xeon Phi clusters. J Supercomput 72:2132. https://doi.org/10.1007/s11227-016-1712-0CrossRef

Luckham D (2008) The power of events: an introduction to complex event processing in distributed enterprise systems. Springer, Berlin

Douglass S, Myers C (2010) Concurrent knowledge activation calculation in large declarative memories. In: Proceedings of the 10th International Conference on Cognitive Modeling, pp 55–60

10.

EsperTech-Esper. http://www.espertech.com/esper/

11.

Russell S, Norvig P (2009) Artificial intelligence: a modern approach, 3rd edn. Prentice Hall, Englewood CliffsMATH

12.

Brailsford SC, Potts CN, Smith BM (1999) Constraint satisfaction problems: algorithms and applications. Eur J Oper Res 119(3):557–581. https://doi.org/10.1016/S0377-2217(98)00364-6CrossRefMATH

13.

Kumar V (1992) Algorithms for constraint satisfaction problems: a survey. AI Mag 13(1):32–44

14.

Atahary T, Taha T, Webber F, Douglass S (2015) Knowledge mining for cognitive agents through path based forward checking. In: International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, pp 5–12

15.

Atahary T, Taha T, Douglass S (2017) Knowledge mining with multiple optimizations on a GPGPU for an autonomous cognitive agent. In: IEEE-2017 SAI Computing Conference (SAI), UK, July 18–20

16.

Zeigler BP, Hammonds PE (2000) Modeling & simulation-based data engineering: introducing pragmatics into ontologies for net-centric information exchange, 1st edn. Academic Press, London

17.

Benavides D, Segura S, Ruiz-Cortés A (2010) Automated analysis of feature models 20 years later: a literature review. Inf Syst 35(6):615–636CrossRef

18.

Gent IP, Jefferson C, Miguel I, Moore NCA, Nightingale P, Prosser P, Unsworth C (2011) A preliminary review of literature on parallel constraint solving. In: Workshop on Parallel Methods for Constraint Solving (PMCS’11)

19.

Gent I, Miguel I, Nightingale P, Mccreesh C, Prosser P, Moore N, Unsworth C (2018) A review of literature on parallel constraint solving. Theory Pract Logic Program 18(5–6):725–758. https://doi.org/10.1017/s1471068418000340MathSciNetCrossRefMATH

20.

Schulte C (2000) Parallel search made simple. In: Proceedings of TRICS: Techniques for Implementing Constraint programming Systems, a Post-Conference Workshop of CP

21.

Bordeaux L, Hamadi Y, Samulowitz H (2009) Experiments with massively parallel constraint solving. In: Boutilier C (ed) IJCAI, pp 443–448

22.

Xie F, Davenport A (2010) Massively parallel constraint programming for supercomputers: challenges and initial results. In: Lodi A, Milano M, Toth P (eds) LNCS, vol 6140. Springer, Heidelberg, pp 334–338

23.

Régin JC, Rezgui M, Malapert A (2014) Improvement of the embarrassingly parallel search for data centers. In: Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, pp 622–635; ISBN 319-10428-7

24.

Caniou Y, Codognet P, Richoux F, Diaz D, Abreu S (2014) Large-scale parallelism for constraint-based local search: the costas array case study. Constraints 20(1):30–56CrossRef

25.

Diaz D, Abreu S, Codognet P (2012) Targeting the cell broadband engine for constraint-based local search. https://doi.org/10.1002/cpe.20oct2012

26.

Diaz D, Abreu S, Codognet P (2010) Parallel constraint-based local search on the Cell/BE multicore architecture. In: Essaaidi M, Malgeri M, Badica C (eds) Intelligent Distributed Computing IV. Studies in Computational Intelligence, vol 315. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15211-5_28

27.

Luong TV, Melab N, Talbi EG (2010) Local search algorithms on graphics processing units, lecture notes in computer science, vol. 6022. Springer, Berlin, pp 264–275

28.

Codognet P, Munera D, Diaz D, Abreu S (2018) Parallel local search. In: Hamadi Y, Sais L (eds) Handbook of parallel constraint reasoning. Springer, Cham

29.

Qiao WB, Créput JC (2019) Massive 2-opt and 3-opt moves with high performance GPU local search to large-scale traveling salesman problem. In: Battiti R, Brunato M, Kotsireas I, Pardalos P (eds) Learning and Intelligent Optimization (LION 12 2018), Lecture Notes in Computer Science, vol 11353. Springer, Cham

30.

Liu K, Löffler S, Hofstedt P (2019) Parallel stochastic portfolio search for constraint solving. In: 2019 IEEE International Conference on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), Xiamen, China, pp 697–704

31.

Archibald B, Maier P, Stewart R, Trinder P (2020) YewPar: skeletons for exact combinatorial search. In: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’20). Association for Computing Machinery, New York, pp 292–307. https://doi.org/10.1145/3332466.3374537

32.

Chu G, Schulte C, Stuckey PJ (2009) Confidence-based work stealing in parallel constraint programming. In: Gent IP (ed) LNCS, vol 5732. Springer, Heidelberg, pp 226–241

33.

Rolf C (2011) Parallelism in constraint programing, PhD Thesis

34.

Rolf CC, Kuchcinski K (2008) State-copying and recomputation in parallel constraint programming with global constraints. In: Parallel, Distributed and Network-Based Processing. IEEE Computer Society, Washington, DC, USA, pp 311–317

35.

GPU AI for Board Games. http://developer.nvidia.com/gpu-ai-board-games. Accessed 10 July 2012

36.

Gianpaolo C, Alessandro M (2012) Complex event processing with T-REX. J Syst Softw 85:1709–1728. https://doi.org/10.1016/j.jss.2012.03.056CrossRef

37.

Huang H, Zhao L, Huang H, Guo S (2019) Machine fault detection for intelligent self-driving networks. IEEE Commun Mag. https://doi.org/10.1109/MCOM.001.1900283CrossRef

38.

Habbas Z, Krajecki M, Singer D (2000) Parallel resolution of CSP with OpenMP. In: Proceedings of the Second European Workshop on OpenMP, Edinburgh, Scotland, pp 1–8

39.

Habbas Z, Krajecki M, Singer D (2001) Shared memory im-plementation of Constraint satisfaction problem resolution. Parallel Process Lett 11(4):487–501CrossRef

40.

Farhang Y, Meybodi MR, Hatamlou AR (2008) Improving the efficiency of forward checking algorithm for solving constraint satisfaction problems. In: Eighth International Conference on Intelligent Systems Design and Applications

41.

Kimmig R, Meyerhenke H, Strash D (2017) Shared memory parallel subgraph enumeration. In: 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Lake Buena Vista, FL, 2017, pp 519–529. https://doi.org/10.1109/ipdpsw.2017.133

42.

Bell 47 helicopter https://en.wikipedia.org/wiki/Bell_47

43.

https://en.wikipedia.org/wiki/Sikorsky_HH-60_Pave_Hawk

44.

https://en.wikipedia.org/wiki/Raytheon_Sentinel

45.

Narendra J, Guillaume R, Xavier L (2008) Choco: an open source java constraint programming library In: Workshop on Open-Source Software for Integer and Constraint Programming

46.

Oakley cluster at Ohio Supercomputer center https://www.osc.edu/supercomputing/computing/oakley

Title: Parallelized path-based search for constraint satisfaction in autonomous cognitive agents
Authors: Tanvir Atahary
Tarek M. Taha
Scott Douglass
Publication date: 24-05-2020
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 2/2021
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-020-03339-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 2/2021

High-performance and deep pedestrian detection based on estimation of different parts

Adoption of human metabolic processes as Data Quality Based Models

A Riccati-type algorithm for solving generalized Hermitian eigenvalue problems

Optimal demultiplexer unit design and energy estimation using quantum dot cellular automata

Optimized clustering-based discovery framework on Internet of Things

Neighborhood search-based job scheduling for IoT big data real-time processing in distributed edge-cloud computing environment

Premium Partner