Bi-objective search with bi-directional A* (Extended Abstract)*

Saman Ahmadi; Guido Tack; Daniel Harabor; Philip Kilby

Bi-objective search with bi-directional A* (Extended Abstract)^*

Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other

11 Citations (Scopus)

Abstract

Bi-objective search is a problem of finding a set of optimal solutions in a two-dimensional domain. This study proposes several enhancements to the state-of-the-art biobjective search with A* and develops its bi-directional variant. Our experimental results on benchmark instances show that our enhanced algorithm is on average five times faster than the state of the art bi-objective search algorithms.

Original language	English
Title of host publication	Fourteenth InternationalSymposium on Combinatorial Search
Editors	Hang Ma, Ivan Serina
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	142-144
Number of pages	3
Volume	12
Edition	1
ISBN (Electronic)	9781713834557, 9781577358701
Publication status	Published - 2021
Event	International Symposium on Combinatorial Search 2021 - Online, Guangzhou, China Duration: 26 Jul 2021 → 30 Jul 2021 Conference number: 14th https://ojs.aaai.org/index.php/SOCS/issue/view/445 (Published Proceedings)

Conference

Conference	International Symposium on Combinatorial Search 2021
Abbreviated title	SoCS 2021
Country/Territory	China
City	Guangzhou
Period	26/07/21 → 30/07/21
Internet address	https://ojs.aaai.org/index.php/SOCS/issue/view/445 (Published Proceedings)

Access to Document

https://ojs.aaai.org/index.php/SOCS/article/view/18563

Cite this

@inproceedings{dccb0a5a63a34f9fb026a55370e4c5de,

title = "Bi-objective search with bi-directional A* (Extended Abstract)*",

abstract = "Bi-objective search is a problem of finding a set of optimal solutions in a two-dimensional domain. This study proposes several enhancements to the state-of-the-art biobjective search with A* and develops its bi-directional variant. Our experimental results on benchmark instances show that our enhanced algorithm is on average five times faster than the state of the art bi-objective search algorithms.",

author = "Saman Ahmadi and Guido Tack and Daniel Harabor and Philip Kilby",

note = "Funding Information: *See our full paper (Ahmadi et al. 2021a) for details. Research at Monash University is supported by the Australian Research Council (ARC) under grant numbers DP190100013 and DP200100025 as well as a gift from Amazon. Copyright {\textcopyright} 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Publisher Copyright: Copyright {\textcopyright} 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; International Symposium on Combinatorial Search 2021, SoCS 2021 ; Conference date: 26-07-2021 Through 30-07-2021",

year = "2021",

language = "English",

volume = "12",

pages = "142--144",

editor = "Hang Ma and Ivan Serina",

booktitle = "Fourteenth InternationalSymposium on Combinatorial Search",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

address = "United States of America",

edition = "1",

url = "https://ojs.aaai.org/index.php/SOCS/issue/view/445",

}

Ahmadi, S, Tack, G , Harabor, D & Kilby, P 2021, Bi-objective search with bi-directional A* (Extended Abstract)^*. in H Ma & I Serina (eds), Fourteenth InternationalSymposium on Combinatorial Search. 1 edn, vol. 12, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 142-144, International Symposium on Combinatorial Search 2021, Guangzhou, China, 26/07/21. <https://ojs.aaai.org/index.php/SOCS/article/view/18563>

Bi-objective search with bi-directional A* (Extended Abstract)^*. / Ahmadi, Saman; Tack, Guido ; Harabor, Daniel et al.
Fourteenth InternationalSymposium on Combinatorial Search. ed. / Hang Ma; Ivan Serina. Vol. 12 1. ed. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI), 2021. p. 142-144.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other

TY - GEN

T1 - Bi-objective search with bi-directional A* (Extended Abstract)*

AU - Ahmadi, Saman

AU - Tack, Guido

AU - Harabor, Daniel

AU - Kilby, Philip

N1 - Conference code: 14th

PY - 2021

Y1 - 2021

N2 - Bi-objective search is a problem of finding a set of optimal solutions in a two-dimensional domain. This study proposes several enhancements to the state-of-the-art biobjective search with A* and develops its bi-directional variant. Our experimental results on benchmark instances show that our enhanced algorithm is on average five times faster than the state of the art bi-objective search algorithms.

AB - Bi-objective search is a problem of finding a set of optimal solutions in a two-dimensional domain. This study proposes several enhancements to the state-of-the-art biobjective search with A* and develops its bi-directional variant. Our experimental results on benchmark instances show that our enhanced algorithm is on average five times faster than the state of the art bi-objective search algorithms.

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

M3 - Conference Paper

AN - SCOPUS:85124592973

VL - 12

SP - 142

EP - 144

BT - Fourteenth InternationalSymposium on Combinatorial Search

A2 - Ma, Hang

A2 - Serina, Ivan

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CA USA

T2 - International Symposium on Combinatorial Search 2021

Y2 - 26 July 2021 through 30 July 2021

ER -

Bi-objective search with bi-directional A* (Extended Abstract)^*

Abstract

Conference

Access to Document

Other files and links

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Cite this

Bi-objective search with bi-directional A* (Extended Abstract)*

Abstract

Conference

Access to Document

Other files and links

Projects

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Cite this

Bi-objective search with bi-directional A* (Extended Abstract)^*