Name
Abstract | ||
|---|---|---|
Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states. The naive technique enumerates the graphs individually. This is equivalent to solving an all-pairs shortest path problem by iterating a single-source algorithm over each source. We introduce a structure, the state agnostic planning graph, that directly, solves the all-pairs problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in classical planning. The more prominent application of tnis technique is in belief-space planning, where an optimization results in drastically improved theoretical complexity. Our experimental evaluation quantifies this performance boost. and demonstrates that heuristic belief-space progression planning using our technique is competitive with the state of t the art. |
Year | Venue | Keywords |
|---|---|---|
2005 | AAAI | all-pairs problem,belief-space planning,classical planning,state agnostic planning graph,tnis technique,all-pairs shortest path problem,naive technique,heuristic information,planning graph,heuristic belief-space progression planning |
Field | DocType | ISBN |
Graph,Heuristic,Any-angle path planning,Mathematical optimization,Shortest path problem,Computer science,Space planning,Artificial intelligence,Machine learning | Conference | 1-57735-236-x |
Citations | PageRank | References |
8 | 0.53 | 23 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| William Cushing | 1 | 132 | 7.18 |
| Daniel Bryce | 2 | 173 | 11.83 |