C-Space tunnel discovery for puzzle path planning

Autor:	Xinya Zhang, Robert Belfer, Paul G. Kry, Etienne Vouga
Rok vydání:	2020
Předmět:	c space Theoretical computer science Computer science Path (graph theory) Configuration space Motion planning Rigid body Heuristics Computer Graphics and Computer-Aided Design Tree (graph theory) Motion (physics)
Zdroj:	ACM Transactions on Graphics. 39
ISSN:	1557-7368 0730-0301
DOI:	10.1145/3386569.3392468
Popis:	Rigid body disentanglement puzzles are challenging for both humans and motion planning algorithms because their solutions involve tricky twisting and sliding moves that correspond to navigating through narrow tunnels in the puzzle's configuration space (C-space). We propose a tunnel-discovery and planning strategy for solving these puzzles. First, we locate important features on the pieces using geometric heuristics and machine learning, and then match pairs of these features to discover collision free states in the puzzle's C-space that lie within the narrow tunnels. Second, we propose a Rapidly-exploring Dense Tree (RDT) motion planner variant that builds tunnel escape roadmaps and then connects these roadmaps into a solution path connecting start and goal states. We evaluate our approach on a variety of challenging disentanglement puzzles and provide extensive baseline comparisons with other motion planning techniques.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::f9c9c3c38534a442060015e3e2b0f388 https://doi.org/10.1145/3386569.3392468 Zobrazit plný text záznamu