@inproceedings{
    Halme2014b,
    author = "Halme, Antti",
    juforank = "NA",
    isbn = "",
    language = "eng",
    title = "A! - A Cooperative Heuristic Search Algorithm",
    country = "",
    abstract = "We propose a new parallel search algorithm – A! – based on cooperating A∗ search agents, concurrency and a secondary tiebreaking heuristic. The search agents in A! share information asynchronously and trade some of their independence for additional search focus and a more global view of the search task. A! is inherently nondeterministic due to the implicit randomness of instruction scheduling, but given a consistent primary heuristic, it still finds optimal solutions for the single-source shortest path problem (SSSP). A! combines into a single cooperative search algorithm the breadth available in parallel execution and the depth-first orientation of both locally and globally informed search. \par We experimentally show that A! outperforms both vanilla A∗ and an explicitly randomized, noncooperative parallel A∗ variant. We present an empirical study on cooperation benefits and scalability in the classic 15-puzzle context. The results imply that cooperation and concurrency can successfully be harnessed in algorithm design, inviting further inquiry into algorithms of this kind.",
    responsibleauthor = "Halme, Antti",
    flags = "TRITON",
    il = "no",
    eventdetails = "7th European Starting AI Researcher Symposium, Prague, the Czech Republic, August 18 - 19, 2014",
    year = "2014",
    keywords = "A*, heuristic search, parallel algorithm, cooperation, nondeterminism",
    unitcode = "T306-100",
    kay = "NA",
    impactfactor = "A4",
    booktitle = "Proceedings, 7th European Starting AI Researcher Symposium"
}