Effective Sampling for Robot Motion Planning Through the Lens of Lattices Article Swipe
Itai Panasoff
,
Kiril Solovey
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2502.04908
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2502.04908
Sampling-based methods for motion planning, which capture the structure of the robot's free space via (typically random) sampling, have gained popularity due to their scalability, simplicity, and for offering global guarantees, such as probabilistic completeness and asymptotic optimality. Unfortunately, the practicality of those guarantees remains limited as they do not provide insights into the behavior of motion planners for a finite number of samples (i.e., a finite running time). In this work, we harness lattice theory and the concept of $(δ,ε)$-completeness by Tsao et al. (2020) to construct deterministic sample sets that endow their planners with strong finite-time guarantees while minimizing running time. In particular, we introduce a highly-efficient deterministic sampling approach based on the $A_d^*$ lattice, which is the best-known geometric covering in dimensions $\leq 21$. Using our new sampling approach, we obtain at least an order-of-magnitude speedup over existing deterministic and uniform random sampling methods for complex motion-planning problems. Overall, our work provides deep mathematical insights while advancing the practical applicability of sampling-based motion planning.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2502.04908
- https://arxiv.org/pdf/2502.04908
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4407310047
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4407310047Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2502.04908Digital Object Identifier
- Title
-
Effective Sampling for Robot Motion Planning Through the Lens of LatticesWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-02-07Full publication date if available
- Authors
-
Itai Panasoff, Kiril SoloveyList of authors in order
- Landing page
-
https://arxiv.org/abs/2502.04908Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2502.04908Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2502.04908Direct OA link when available
- Concepts
-
Lens (geology), Computer vision, Sampling (signal processing), Robot, Computer science, Motion (physics), Motion planning, Artificial intelligence, Optics, Physics, Filter (signal processing)Top concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4407310047 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2502.04908 |
| ids.doi | https://doi.org/10.48550/arxiv.2502.04908 |
| ids.openalex | https://openalex.org/W4407310047 |
| fwci | |
| type | preprint |
| title | Effective Sampling for Robot Motion Planning Through the Lens of Lattices |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12072 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.8780999779701233 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Machine Learning and Algorithms |
| topics[1].id | https://openalex.org/T10586 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.8166000247001648 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1707 |
| topics[1].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[1].display_name | Robotic Path Planning Algorithms |
| topics[2].id | https://openalex.org/T10906 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.7889999747276306 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1702 |
| topics[2].subfield.display_name | Artificial Intelligence |
| topics[2].display_name | AI-based Problem Solving and Planning |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C15336307 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6321790218353271 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1766051 |
| concepts[0].display_name | Lens (geology) |
| concepts[1].id | https://openalex.org/C31972630 |
| concepts[1].level | 1 |
| concepts[1].score | 0.6029253602027893 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q844240 |
| concepts[1].display_name | Computer vision |
| concepts[2].id | https://openalex.org/C140779682 |
| concepts[2].level | 3 |
| concepts[2].score | 0.5924971103668213 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q210868 |
| concepts[2].display_name | Sampling (signal processing) |
| concepts[3].id | https://openalex.org/C90509273 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5595735311508179 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q11012 |
| concepts[3].display_name | Robot |
| concepts[4].id | https://openalex.org/C41008148 |
| concepts[4].level | 0 |
| concepts[4].score | 0.5367169976234436 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[4].display_name | Computer science |
| concepts[5].id | https://openalex.org/C104114177 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5179733037948608 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q79782 |
| concepts[5].display_name | Motion (physics) |
| concepts[6].id | https://openalex.org/C81074085 |
| concepts[6].level | 3 |
| concepts[6].score | 0.5178806781768799 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q366872 |
| concepts[6].display_name | Motion planning |
| concepts[7].id | https://openalex.org/C154945302 |
| concepts[7].level | 1 |
| concepts[7].score | 0.5053537487983704 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[7].display_name | Artificial intelligence |
| concepts[8].id | https://openalex.org/C120665830 |
| concepts[8].level | 1 |
| concepts[8].score | 0.23474466800689697 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q14620 |
| concepts[8].display_name | Optics |
| concepts[9].id | https://openalex.org/C121332964 |
| concepts[9].level | 0 |
| concepts[9].score | 0.21140089631080627 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[9].display_name | Physics |
| concepts[10].id | https://openalex.org/C106131492 |
| concepts[10].level | 2 |
| concepts[10].score | 0.0 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q3072260 |
| concepts[10].display_name | Filter (signal processing) |
| keywords[0].id | https://openalex.org/keywords/lens |
| keywords[0].score | 0.6321790218353271 |
| keywords[0].display_name | Lens (geology) |
| keywords[1].id | https://openalex.org/keywords/computer-vision |
| keywords[1].score | 0.6029253602027893 |
| keywords[1].display_name | Computer vision |
| keywords[2].id | https://openalex.org/keywords/sampling |
| keywords[2].score | 0.5924971103668213 |
| keywords[2].display_name | Sampling (signal processing) |
| keywords[3].id | https://openalex.org/keywords/robot |
| keywords[3].score | 0.5595735311508179 |
| keywords[3].display_name | Robot |
| keywords[4].id | https://openalex.org/keywords/computer-science |
| keywords[4].score | 0.5367169976234436 |
| keywords[4].display_name | Computer science |
| keywords[5].id | https://openalex.org/keywords/motion |
| keywords[5].score | 0.5179733037948608 |
| keywords[5].display_name | Motion (physics) |
| keywords[6].id | https://openalex.org/keywords/motion-planning |
| keywords[6].score | 0.5178806781768799 |
| keywords[6].display_name | Motion planning |
| keywords[7].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[7].score | 0.5053537487983704 |
| keywords[7].display_name | Artificial intelligence |
| keywords[8].id | https://openalex.org/keywords/optics |
| keywords[8].score | 0.23474466800689697 |
| keywords[8].display_name | Optics |
| keywords[9].id | https://openalex.org/keywords/physics |
| keywords[9].score | 0.21140089631080627 |
| keywords[9].display_name | Physics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2502.04908 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2502.04908 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2502.04908 |
| locations[1].id | doi:10.48550/arxiv.2502.04908 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2502.04908 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5044807100 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Itai Panasoff |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Panasoff, Itai |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5000480439 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-0254-0572 |
| authorships[1].author.display_name | Kiril Solovey |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Solovey, Kiril |
| authorships[1].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2502.04908 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Effective Sampling for Robot Motion Planning Through the Lens of Lattices |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12072 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.8780999779701233 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Machine Learning and Algorithms |
| related_works | https://openalex.org/W3049557657, https://openalex.org/W3150915502, https://openalex.org/W8302103, https://openalex.org/W2111158727, https://openalex.org/W2354263513, https://openalex.org/W1809059965, https://openalex.org/W2024668666, https://openalex.org/W3171631314, https://openalex.org/W2155287816, https://openalex.org/W2674584172 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2502.04908 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2502.04908 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2502.04908 |
| primary_location.id | pmh:oai:arXiv.org:2502.04908 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2502.04908 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2502.04908 |
| publication_date | 2025-02-07 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 59, 65, 107 |
| abstract_inverted_index.In | 69, 103 |
| abstract_inverted_index.an | 136 |
| abstract_inverted_index.as | 32, 46 |
| abstract_inverted_index.at | 134 |
| abstract_inverted_index.by | 81 |
| abstract_inverted_index.do | 48 |
| abstract_inverted_index.et | 83 |
| abstract_inverted_index.in | 123 |
| abstract_inverted_index.is | 118 |
| abstract_inverted_index.of | 9, 41, 55, 62, 79, 163 |
| abstract_inverted_index.on | 113 |
| abstract_inverted_index.to | 22, 86 |
| abstract_inverted_index.we | 72, 105, 132 |
| abstract_inverted_index.al. | 84 |
| abstract_inverted_index.and | 26, 35, 76, 142 |
| abstract_inverted_index.due | 21 |
| abstract_inverted_index.for | 2, 27, 58, 147 |
| abstract_inverted_index.new | 129 |
| abstract_inverted_index.not | 49 |
| abstract_inverted_index.our | 128, 152 |
| abstract_inverted_index.the | 7, 10, 39, 53, 77, 114, 119, 160 |
| abstract_inverted_index.via | 14 |
| abstract_inverted_index.21$. | 126 |
| abstract_inverted_index.Tsao | 82 |
| abstract_inverted_index.deep | 155 |
| abstract_inverted_index.free | 12 |
| abstract_inverted_index.have | 18 |
| abstract_inverted_index.into | 52 |
| abstract_inverted_index.over | 139 |
| abstract_inverted_index.sets | 90 |
| abstract_inverted_index.such | 31 |
| abstract_inverted_index.that | 91 |
| abstract_inverted_index.they | 47 |
| abstract_inverted_index.this | 70 |
| abstract_inverted_index.with | 95 |
| abstract_inverted_index.work | 153 |
| abstract_inverted_index.$\leq | 125 |
| abstract_inverted_index.Using | 127 |
| abstract_inverted_index.based | 112 |
| abstract_inverted_index.endow | 92 |
| abstract_inverted_index.least | 135 |
| abstract_inverted_index.space | 13 |
| abstract_inverted_index.their | 23, 93 |
| abstract_inverted_index.those | 42 |
| abstract_inverted_index.time. | 102 |
| abstract_inverted_index.which | 5, 117 |
| abstract_inverted_index.while | 99, 158 |
| abstract_inverted_index.work, | 71 |
| abstract_inverted_index.(2020) | 85 |
| abstract_inverted_index.(i.e., | 64 |
| abstract_inverted_index.finite | 60, 66 |
| abstract_inverted_index.gained | 19 |
| abstract_inverted_index.global | 29 |
| abstract_inverted_index.motion | 3, 56, 165 |
| abstract_inverted_index.number | 61 |
| abstract_inverted_index.obtain | 133 |
| abstract_inverted_index.random | 144 |
| abstract_inverted_index.sample | 89 |
| abstract_inverted_index.strong | 96 |
| abstract_inverted_index.theory | 75 |
| abstract_inverted_index.time). | 68 |
| abstract_inverted_index.$A_d^*$ | 115 |
| abstract_inverted_index.capture | 6 |
| abstract_inverted_index.complex | 148 |
| abstract_inverted_index.concept | 78 |
| abstract_inverted_index.harness | 73 |
| abstract_inverted_index.lattice | 74 |
| abstract_inverted_index.limited | 45 |
| abstract_inverted_index.methods | 1, 146 |
| abstract_inverted_index.provide | 50 |
| abstract_inverted_index.random) | 16 |
| abstract_inverted_index.remains | 44 |
| abstract_inverted_index.robot's | 11 |
| abstract_inverted_index.running | 67, 101 |
| abstract_inverted_index.samples | 63 |
| abstract_inverted_index.speedup | 138 |
| abstract_inverted_index.uniform | 143 |
| abstract_inverted_index.Overall, | 151 |
| abstract_inverted_index.approach | 111 |
| abstract_inverted_index.behavior | 54 |
| abstract_inverted_index.covering | 122 |
| abstract_inverted_index.existing | 140 |
| abstract_inverted_index.insights | 51, 157 |
| abstract_inverted_index.lattice, | 116 |
| abstract_inverted_index.offering | 28 |
| abstract_inverted_index.planners | 57, 94 |
| abstract_inverted_index.provides | 154 |
| abstract_inverted_index.sampling | 110, 130, 145 |
| abstract_inverted_index.advancing | 159 |
| abstract_inverted_index.approach, | 131 |
| abstract_inverted_index.construct | 87 |
| abstract_inverted_index.geometric | 121 |
| abstract_inverted_index.introduce | 106 |
| abstract_inverted_index.planning, | 4 |
| abstract_inverted_index.planning. | 166 |
| abstract_inverted_index.practical | 161 |
| abstract_inverted_index.problems. | 150 |
| abstract_inverted_index.sampling, | 17 |
| abstract_inverted_index.structure | 8 |
| abstract_inverted_index.(typically | 15 |
| abstract_inverted_index.asymptotic | 36 |
| abstract_inverted_index.best-known | 120 |
| abstract_inverted_index.dimensions | 124 |
| abstract_inverted_index.guarantees | 43, 98 |
| abstract_inverted_index.minimizing | 100 |
| abstract_inverted_index.popularity | 20 |
| abstract_inverted_index.finite-time | 97 |
| abstract_inverted_index.guarantees, | 30 |
| abstract_inverted_index.optimality. | 37 |
| abstract_inverted_index.particular, | 104 |
| abstract_inverted_index.simplicity, | 25 |
| abstract_inverted_index.completeness | 34 |
| abstract_inverted_index.mathematical | 156 |
| abstract_inverted_index.practicality | 40 |
| abstract_inverted_index.scalability, | 24 |
| abstract_inverted_index.applicability | 162 |
| abstract_inverted_index.deterministic | 88, 109, 141 |
| abstract_inverted_index.probabilistic | 33 |
| abstract_inverted_index.Sampling-based | 0 |
| abstract_inverted_index.Unfortunately, | 38 |
| abstract_inverted_index.sampling-based | 164 |
| abstract_inverted_index.motion-planning | 149 |
| abstract_inverted_index.highly-efficient | 108 |
| abstract_inverted_index.order-of-magnitude | 137 |
| abstract_inverted_index.$(δ,ε)$-completeness | 80 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |