A Knowledge Parallel Heuristic Search Algorithm in Ubiquitous Creativity System

Heuristic search in ubiquitous knowledge systems is an important technique in artificial intelligence. The best-first branch-and-bound algorithm is not only the most general search algorithm, but also one of a few general algorithms which can be used to solve a wide range of nondeterministic polynomial (NP)-hard processors. The algorithm can be parallelized by using a loosely-coupled network of processors. In this distributed algorithm, each processor maintains a local OPEN list and processes its implementation. The processors are required to exchange nodes of their local OPEN lists. One of the effective methods of exchanging information between processors is by using a BLACKBOARD. However, the BLACKBOARD requires shared memory. In this paper, the authors present a distributed algorithm using Binary Multi-Level Multi-Access (BMLMA) communication protocol. The communication network of BMLMA provides the global sorting of messages as a by-product of the protocol. Logically, this is analogous to a global associative memory: thus, it can be used to implement a logical associative BLACKBOARD. Computer simulation using a traveling salesman problem has confirmed the linear scalability of proposed algorithm.

• Corporate Authors:

  ITS Japan

  Tokyo,   Japan 

  ITS America

  1100 17th Street, NW, 12th Floor
  Washington, DC  United States  20036

  ERTICO

  326 Avenue Louis
  Brussels,   Belgium  B-1050
• Authors:
  • Jung, Chang-Duk
  • Park, You-Keun
  • Jeon, Hye-Jeong
• Conference:
  • 17th ITS World Congress
  • Location: Busan , Korea, South
  • Date: 2010-10-25 to 2010-10-29
• Publication Date: 2010

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; References;
• Pagination: 12p
• Monograph Title: 17th ITS World Congress, Busan, 2010: Proceedings

Subject/Index Terms

• TRT Terms: Artificial intelligence; Branch and bound algorithms; Heuristic methods; Information technology
• Subject Areas: Data and Information Technology; Highways; I70: Traffic and Transport;

Filing Info

• Accession Number: 01368344
• Record Type: Publication
• Files: TRIS
• Created Date: Apr 25 2012 7:57AM