Pushing blocks is hard. (Q1395573): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q3154375 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4232783 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: SOKOBAN and other motion planning problems / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4198056 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Parallel concepts in graph theory / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4401030 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Motion planning in the presence of movable obstacles / rank | |||
Normal rank | |||
Revision as of 17:13, 5 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Pushing blocks is hard. |
scientific article |
Statements
Pushing blocks is hard. (English)
0 references
1 July 2003
0 references
The authors study several variations of simpler puzzles and show that the models are NP-hard. The results subsume a number of previous NP-hardness proofs of pushing-block variations, and solve the Push-X open problem. The main idea in the is to force the robot to follow constrained Eulerian tours of planar graphs and carry a constant amount of information along each edge of the graph. Moreover it is build a kind of logic engine. This approach is innovative and contrast with other previous approaches of building circuits based on graphs.
0 references
computational complexity
0 references
computational geometry
0 references
motion planning
0 references
combinatorial games
0 references
NP-hard
0 references
push-X open problem
0 references
robot
0 references
Eulerian tours of planar graphs
0 references
