Parallel Best-First Search of State-Space Graphs: A Summary of Results

Vipin Kumar; K. Ramesh; V. Nageshwara Rao

Parallel Best-First Search of State-Space Graphs: A Summary of Results

Vipin Kumar, K. Ramesh, V. Nageshwara Rao

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper presents many different parallel formulations of the A*/Branch-and-Bound search algorithm. The parallel formulations primarily differ in the data structures used. Some formulations are suited only for shared-memory architectures, whereas others are suited for distributed-memory architectures as well. These parallel formulations have been implemented to solve the vertex cover problem and the TSP problem on the BBN Butterfly parallel processor. Using appropriate data structures, we are able to obtain fairly linear speedups for as many as 100 processors. We also discovered problem characteristics that make certain formulations more (or less) suitable for some search problems. Since the best-first search paradigm of A*/Branch-and-Bound is very commonly used, we expect these parallel formulations to be effective for a variety of problems. Concurrent and distributed priority queues used in these parallel formulations can be used in many parallel algorithms other than parallel A*/branch-and-bound.

Original language	English (US)
Title of host publication	Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988
Publisher	AAAI press
Pages	122-127
Number of pages	6
ISBN (Electronic)	0262510553, 9780262510554
State	Published - 1988
Externally published	Yes
Event	7th National Conference on Artificial Intelligence, AAAI 1988 - St. Paul, United States Duration: Aug 21 1988 → Aug 26 1988

Publication series

Name	Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988

Conference

Conference	7th National Conference on Artificial Intelligence, AAAI 1988
Country/Territory	United States
City	St. Paul
Period	8/21/88 → 8/26/88

Bibliographical note

Funding Information:
*This work was supported by Army Research Office grant # DAAG29-84-K-0060 to the Artificial Intelligence Laboratory, and Office of Naval Research Grant N00014-86-K-0763 to the computer science department at the University of Texas at Austin.

Publisher Copyright:
Copyright © 1988, AAAI (www.aaai.org). All rights reserved.

Find It

Find It at U of M Libraries

Cite this

Parallel Best-First Search of State-Space Graphs: A Summary of Results. / Kumar, Vipin; Ramesh, K.; Rao, V. Nageshwara.
Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988. AAAI press, 1988. p. 122-127 (Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kumar, V, Ramesh, K & Rao, VN 1988, Parallel Best-First Search of State-Space Graphs: A Summary of Results. in Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988. Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988, AAAI press, pp. 122-127, 7th National Conference on Artificial Intelligence, AAAI 1988, St. Paul, United States, 8/21/88.

@inproceedings{91d50dfe10354cc18f9a3e0fa9a206dc,

title = "Parallel Best-First Search of State-Space Graphs: A Summary of Results",

abstract = "This paper presents many different parallel formulations of the A*/Branch-and-Bound search algorithm. The parallel formulations primarily differ in the data structures used. Some formulations are suited only for shared-memory architectures, whereas others are suited for distributed-memory architectures as well. These parallel formulations have been implemented to solve the vertex cover problem and the TSP problem on the BBN Butterfly parallel processor. Using appropriate data structures, we are able to obtain fairly linear speedups for as many as 100 processors. We also discovered problem characteristics that make certain formulations more (or less) suitable for some search problems. Since the best-first search paradigm of A*/Branch-and-Bound is very commonly used, we expect these parallel formulations to be effective for a variety of problems. Concurrent and distributed priority queues used in these parallel formulations can be used in many parallel algorithms other than parallel A*/branch-and-bound.",

author = "Vipin Kumar and K. Ramesh and Rao, {V. Nageshwara}",

note = "Funding Information: *This work was supported by Army Research Office grant # DAAG29-84-K-0060 to the Artificial Intelligence Laboratory, and Office of Naval Research Grant N00014-86-K-0763 to the computer science department at the University of Texas at Austin. Publisher Copyright: Copyright {\textcopyright} 1988, AAAI (www.aaai.org). All rights reserved.; 7th National Conference on Artificial Intelligence, AAAI 1988 ; Conference date: 21-08-1988 Through 26-08-1988",

year = "1988",

language = "English (US)",

series = "Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988",

publisher = "AAAI press",

pages = "122--127",

booktitle = "Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988",

}

TY - GEN

T1 - Parallel Best-First Search of State-Space Graphs

T2 - 7th National Conference on Artificial Intelligence, AAAI 1988

AU - Kumar, Vipin

AU - Ramesh, K.

AU - Rao, V. Nageshwara

N1 - Funding Information: *This work was supported by Army Research Office grant # DAAG29-84-K-0060 to the Artificial Intelligence Laboratory, and Office of Naval Research Grant N00014-86-K-0763 to the computer science department at the University of Texas at Austin. Publisher Copyright: Copyright © 1988, AAAI (www.aaai.org). All rights reserved.

PY - 1988

Y1 - 1988

N2 - This paper presents many different parallel formulations of the A*/Branch-and-Bound search algorithm. The parallel formulations primarily differ in the data structures used. Some formulations are suited only for shared-memory architectures, whereas others are suited for distributed-memory architectures as well. These parallel formulations have been implemented to solve the vertex cover problem and the TSP problem on the BBN Butterfly parallel processor. Using appropriate data structures, we are able to obtain fairly linear speedups for as many as 100 processors. We also discovered problem characteristics that make certain formulations more (or less) suitable for some search problems. Since the best-first search paradigm of A*/Branch-and-Bound is very commonly used, we expect these parallel formulations to be effective for a variety of problems. Concurrent and distributed priority queues used in these parallel formulations can be used in many parallel algorithms other than parallel A*/branch-and-bound.

AB - This paper presents many different parallel formulations of the A*/Branch-and-Bound search algorithm. The parallel formulations primarily differ in the data structures used. Some formulations are suited only for shared-memory architectures, whereas others are suited for distributed-memory architectures as well. These parallel formulations have been implemented to solve the vertex cover problem and the TSP problem on the BBN Butterfly parallel processor. Using appropriate data structures, we are able to obtain fairly linear speedups for as many as 100 processors. We also discovered problem characteristics that make certain formulations more (or less) suitable for some search problems. Since the best-first search paradigm of A*/Branch-and-Bound is very commonly used, we expect these parallel formulations to be effective for a variety of problems. Concurrent and distributed priority queues used in these parallel formulations can be used in many parallel algorithms other than parallel A*/branch-and-bound.

UR - http://www.scopus.com/inward/record.url?scp=85156257600&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85156257600&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85156257600

T3 - Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988

SP - 122

EP - 127

BT - Proceedings of the 7th National Conference on Artificial Intelligence, AAAI 1988

PB - AAAI press

Y2 - 21 August 1988 through 26 August 1988

ER -

Parallel Best-First Search of State-Space Graphs: A Summary of Results

Abstract

Publication series

Conference

Bibliographical note

Find It

Other files and links

Fingerprint

Cite this