Abstraction-based action ordering in planning

M. Fox, D. Long, J. Porteous

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Citations (Scopus)

Abstract

Many planning problems contain collections of symmetric objects, actions and structures which render them difficult to solve efficiently. It has been shown that the detection and exploitation of symmetric structure in planning problems can dramatically reduce the size of the search space and the time taken to find a solution. We present the idea of using an abstraction of the problem domain to reveal symmetric structure and guide the navigation of the search space. We show that this is effective even in domains in which there is little accessible symmetric structure available for pruning. Proactive exploitation represents a flexible and powerfulalternative to the symmetry-breaking strategies exploited in earlier work in planning and CSPs. The notion of almost symmetry is defined and results are presented showing that proactive exploitation of almost symmetry can improve the performance of a heuristic forward search planner.
LanguageEnglish
Title of host publicationProceedings of the International Joint Conferences on Artificial Intelligence (IJCAI-05)
Number of pages6
Publication statusPublished - 2005

Fingerprint

exploitation
planning
navigation
broken symmetry
symmetry

Keywords

  • planning
  • abstraction
  • navigation
  • searching
  • symmetry
  • information retrieval

Cite this

Fox, M., Long, D., & Porteous, J. (2005). Abstraction-based action ordering in planning. In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI-05)
Fox, M. ; Long, D. ; Porteous, J. / Abstraction-based action ordering in planning. Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI-05). 2005.
@inbook{9210f0e8ac3e439fbfb2238c8f32c5ef,
title = "Abstraction-based action ordering in planning",
abstract = "Many planning problems contain collections of symmetric objects, actions and structures which render them difficult to solve efficiently. It has been shown that the detection and exploitation of symmetric structure in planning problems can dramatically reduce the size of the search space and the time taken to find a solution. We present the idea of using an abstraction of the problem domain to reveal symmetric structure and guide the navigation of the search space. We show that this is effective even in domains in which there is little accessible symmetric structure available for pruning. Proactive exploitation represents a flexible and powerfulalternative to the symmetry-breaking strategies exploited in earlier work in planning and CSPs. The notion of almost symmetry is defined and results are presented showing that proactive exploitation of almost symmetry can improve the performance of a heuristic forward search planner.",
keywords = "planning, abstraction, navigation, searching, symmetry, information retrieval",
author = "M. Fox and D. Long and J. Porteous",
year = "2005",
language = "English",
booktitle = "Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI-05)",

}

Fox, M, Long, D & Porteous, J 2005, Abstraction-based action ordering in planning. in Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI-05).

Abstraction-based action ordering in planning. / Fox, M.; Long, D.; Porteous, J.

Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI-05). 2005.

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - Abstraction-based action ordering in planning

AU - Fox, M.

AU - Long, D.

AU - Porteous, J.

PY - 2005

Y1 - 2005

N2 - Many planning problems contain collections of symmetric objects, actions and structures which render them difficult to solve efficiently. It has been shown that the detection and exploitation of symmetric structure in planning problems can dramatically reduce the size of the search space and the time taken to find a solution. We present the idea of using an abstraction of the problem domain to reveal symmetric structure and guide the navigation of the search space. We show that this is effective even in domains in which there is little accessible symmetric structure available for pruning. Proactive exploitation represents a flexible and powerfulalternative to the symmetry-breaking strategies exploited in earlier work in planning and CSPs. The notion of almost symmetry is defined and results are presented showing that proactive exploitation of almost symmetry can improve the performance of a heuristic forward search planner.

AB - Many planning problems contain collections of symmetric objects, actions and structures which render them difficult to solve efficiently. It has been shown that the detection and exploitation of symmetric structure in planning problems can dramatically reduce the size of the search space and the time taken to find a solution. We present the idea of using an abstraction of the problem domain to reveal symmetric structure and guide the navigation of the search space. We show that this is effective even in domains in which there is little accessible symmetric structure available for pruning. Proactive exploitation represents a flexible and powerfulalternative to the symmetry-breaking strategies exploited in earlier work in planning and CSPs. The notion of almost symmetry is defined and results are presented showing that proactive exploitation of almost symmetry can improve the performance of a heuristic forward search planner.

KW - planning

KW - abstraction

KW - navigation

KW - searching

KW - symmetry

KW - information retrieval

UR - http://www.ijcai.org/proceedings05.html

UR - http://www.ijcai.org/papers/0608.pdf

M3 - Chapter

BT - Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI-05)

ER -

Fox M, Long D, Porteous J. Abstraction-based action ordering in planning. In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI-05). 2005