Grant: Discovery Grants Program - Individual
University of Alberta
$42,000.00
High-Performance Domain-Independent Heuristic Search
EF 2012-13
Résumé
The most familiar example of a ""state space search"" problem is GPS navigation: a person is at some location and needs to find a path to a different location. A similar problem occurs in many computer games, when an agent needs to find a path from one place to another in the game map. Puzzles, like Rubik's Cube, are another example. Here the different arrangements of the puzzle are analogous to the locations in a map and the moves that change the puzzle's arrangement are analogous to the road segments that connect locations in a map. The objective is the same - to find a path (sequence of moves) that changes the puzzle from its initial arrangement to a specific desired arrangement. There are many important real-world problems that can be cast as state space search problems. Examples include logistics problems, such as parcel pickup and delivery routing, and manufacturing problems, such as finding the least expensive, or fastest, way to manufacture or assemble a given product, given the machines available in the manufacturing plant.
My research aims to develop computer algorithms that can quickly solve a broad family of state space search problems without human intervention. The system is given a description of what states (arrangements, locations, etc.) are possible and the operators that are available to transform one state into another. Its objective is to find a sequence of operators (""a solution"") that transforms the given state into a state that satisfies certain given properties (the ""goal""). It does this by analyzing the given information and creating ""heuristic"" information - information that can guide it so that it quickly finds a solution. In my research the heuristic information typically takes the form of a function that estimates the cost to achieve the goal from any given state. My proposed research has three objectives: (1) to improve existing methods and invent new ones if the existing ones are inadequate; (2) to adapt these methods so that they work well when each operator has a different cost; and (3) to generalize these methods so they work well on a broader family of problems.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Alberta, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
46246-2012
Name nom
Holte, Robert
Department département
Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2012
Award amount
42000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Partie
1
Nb partie
5
Application title
High-Performance Domain-Independent Heuristic Search
Keyword
NSERC
Application summary
The most familiar example of a ""state space search"" problem is GPS navigation: a person is at some location and needs to find a path to a different location. A similar problem occurs in many computer games, when an agent needs to find a path from one place to another in the game map. Puzzles, like Rubik's Cube, are another example. Here the different arrangements of the puzzle are analogous to the locations in a map and the moves that change the puzzle's arrangement are analogous to the road segments that connect locations in a map. The objective is the same - to find a path (sequence of moves) that changes the puzzle from its initial arrangement to a specific desired arrangement. There are many important real-world problems that can be cast as state space search problems. Examples include logistics problems, such as parcel pickup and delivery routing, and manufacturing problems, such as finding the least expensive, or fastest, way to manufacture or assemble a given product, given the machines available in the manufacturing plant.
My research aims to develop computer algorithms that can quickly solve a broad family of state space search problems without human intervention. The system is given a description of what states (arrangements, locations, etc.) are possible and the operators that are available to transform one state into another. Its objective is to find a sequence of operators (""a solution"") that transforms the given state into a state that satisfies certain given properties (the ""goal""). It does this by analyzing the given information and creating ""heuristic"" information - information that can guide it so that it quickly finds a solution. In my research the heuristic information typically takes the form of a function that estimates the cost to achieve the goal from any given state. My proposed research has three objectives: (1) to improve existing methods and invent new ones if the existing ones are inadequate; (2) to adapt these methods so that they work well when each operator has a different cost; and (3) to generalize these methods so they work well on a broader family of problems.