Forming Large Patterns with Local Robots in the OBLOT Model Article Swipe
Christopher Hahn
,
Jonas Harbig
,
Peter Kling
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2404.02771
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2404.02771
In the arbitrary pattern formation problem, $n$ autonomous, mobile robots must form an arbitrary pattern $P \subseteq \mathbb{R}^2$. The (deterministic) robots are typically assumed to be indistinguishable, disoriented, and unable to communicate. An important distinction is whether robots have memory and/or a limited viewing range. Previous work managed to form $P$ under a natural symmetry condition if robots have no memory but an unlimited viewing range [22] or if robots have a limited viewing range but memory [25]. In the latter case, $P$ is only formed in a shrunk version that has constant diameter. Without memory and with limited viewing range, forming arbitrary patterns remains an open problem. We provide a partial solution by showing that $P$ can be formed under the same symmetry condition if the robots' initial diameter is $\leq 1$. Our protocol partitions $P$ into rotation-symmetric components and exploits the initial mutual visibility to form one cluster per component. Using a careful placement of the clusters and their robots, we show that a cluster can move in a coordinated way through its component while drawing $P$ by dropping one robot per pattern coordinate.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4394006970
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4394006970Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2404.02771Digital Object Identifier
- Title
-
Forming Large Patterns with Local Robots in the OBLOT ModelWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-04-03Full publication date if available
- Authors
-
Christopher Hahn, Jonas Harbig, Peter KlingList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14Direct OA link when available
- Concepts
-
Robot, Computer science, Artificial intelligenceTop 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/W4394006970 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2404.02771 |
| ids.doi | https://doi.org/10.48550/arxiv.2404.02771 |
| ids.openalex | https://openalex.org/W4394006970 |
| fwci | |
| type | preprint |
| title | Forming Large Patterns with Local Robots in the OBLOT Model |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12784 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9771999716758728 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2210 |
| topics[0].subfield.display_name | Mechanical Engineering |
| topics[0].display_name | Modular Robots and Swarm Intelligence |
| topics[1].id | https://openalex.org/T12288 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.909600019454956 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Optimization and Search Problems |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C90509273 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7148435115814209 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q11012 |
| concepts[0].display_name | Robot |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.4502807855606079 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C154945302 |
| concepts[2].level | 1 |
| concepts[2].score | 0.3322499096393585 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[2].display_name | Artificial intelligence |
| keywords[0].id | https://openalex.org/keywords/robot |
| keywords[0].score | 0.7148435115814209 |
| keywords[0].display_name | Robot |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.4502807855606079 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[2].score | 0.3322499096393585 |
| keywords[2].display_name | Artificial intelligence |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:19892 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306402524 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| locations[0].source.host_organization | https://openalex.org/I2799853480 |
| locations[0].source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| locations[0].source.host_organization_lineage | https://openalex.org/I2799853480 |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | InProceedings |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14 |
| locations[1].id | pmh:oai:arXiv.org:2404.02771 |
| 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 | |
| locations[1].pdf_url | https://arxiv.org/pdf/2404.02771 |
| locations[1].version | submittedVersion |
| locations[1].raw_type | |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | http://arxiv.org/abs/2404.02771 |
| locations[2].id | doi:10.48550/arxiv.2404.02771 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400194 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | True |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | arXiv (Cornell University) |
| locations[2].source.host_organization | https://openalex.org/I205783295 |
| locations[2].source.host_organization_name | Cornell University |
| locations[2].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[2].license | cc-by |
| locations[2].pdf_url | |
| locations[2].version | |
| locations[2].raw_type | article |
| locations[2].license_id | https://openalex.org/licenses/cc-by |
| locations[2].is_accepted | False |
| locations[2].is_published | |
| locations[2].raw_source_name | |
| locations[2].landing_page_url | https://doi.org/10.48550/arxiv.2404.02771 |
| locations[3].id | doi:10.4230/lipics.sand.2024.14 |
| locations[3].is_oa | True |
| locations[3].source.id | https://openalex.org/S7407052059 |
| locations[3].source.type | repository |
| locations[3].source.is_oa | False |
| locations[3].source.issn_l | |
| locations[3].source.is_core | False |
| locations[3].source.is_in_doaj | False |
| locations[3].source.display_name | Dagstuhl Research Online Publication Server |
| locations[3].source.host_organization | |
| locations[3].source.host_organization_name | |
| locations[3].license | cc-by |
| locations[3].pdf_url | |
| locations[3].version | |
| locations[3].raw_type | |
| locations[3].license_id | https://openalex.org/licenses/cc-by |
| locations[3].is_accepted | False |
| locations[3].is_published | |
| locations[3].raw_source_name | |
| locations[3].landing_page_url | https://doi.org/10.4230/lipics.sand.2024.14 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5103082632 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-1243-4880 |
| authorships[0].author.display_name | Christopher Hahn |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Hahn, Christopher |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5058331868 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-3943-5979 |
| authorships[1].author.display_name | Jonas Harbig |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Harbig, Jonas |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5007675663 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-0000-8689 |
| authorships[2].author.display_name | Peter Kling |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Kling, Peter |
| authorships[2].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://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2024-04-06T00:00:00 |
| display_name | Forming Large Patterns with Local Robots in the OBLOT Model |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12784 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9771999716758728 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2210 |
| primary_topic.subfield.display_name | Mechanical Engineering |
| primary_topic.display_name | Modular Robots and Swarm Intelligence |
| related_works | https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W2478288626, https://openalex.org/W4391913857, https://openalex.org/W2350741829, https://openalex.org/W2530322880 |
| cited_by_count | 0 |
| locations_count | 4 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:19892 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306402524 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| 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 | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| best_oa_location.source.host_organization | https://openalex.org/I2799853480 |
| best_oa_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | InProceedings |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:19892 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306402524 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| primary_location.source.host_organization | https://openalex.org/I2799853480 |
| primary_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| primary_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | InProceedings |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.14 |
| publication_date | 2024-04-03 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 41, 52, 71, 87, 110, 153, 165, 170 |
| abstract_inverted_index.$P | 15 |
| abstract_inverted_index.An | 32 |
| abstract_inverted_index.In | 0, 78 |
| abstract_inverted_index.We | 108 |
| abstract_inverted_index.an | 12, 62, 105 |
| abstract_inverted_index.be | 25, 118 |
| abstract_inverted_index.by | 113, 179 |
| abstract_inverted_index.if | 56, 68, 125 |
| abstract_inverted_index.in | 86, 169 |
| abstract_inverted_index.is | 35, 83, 130 |
| abstract_inverted_index.no | 59 |
| abstract_inverted_index.of | 156 |
| abstract_inverted_index.or | 67 |
| abstract_inverted_index.to | 24, 30, 48, 146 |
| abstract_inverted_index.we | 162 |
| abstract_inverted_index.$P$ | 50, 82, 116, 136, 178 |
| abstract_inverted_index.$n$ | 6 |
| abstract_inverted_index.1$. | 132 |
| abstract_inverted_index.Our | 133 |
| abstract_inverted_index.The | 18 |
| abstract_inverted_index.and | 28, 96, 140, 159 |
| abstract_inverted_index.are | 21 |
| abstract_inverted_index.but | 61, 75 |
| abstract_inverted_index.can | 117, 167 |
| abstract_inverted_index.has | 91 |
| abstract_inverted_index.its | 174 |
| abstract_inverted_index.one | 148, 181 |
| abstract_inverted_index.per | 150, 183 |
| abstract_inverted_index.the | 1, 79, 121, 126, 142, 157 |
| abstract_inverted_index.way | 172 |
| abstract_inverted_index.[22] | 66 |
| abstract_inverted_index.form | 11, 49, 147 |
| abstract_inverted_index.have | 38, 58, 70 |
| abstract_inverted_index.into | 137 |
| abstract_inverted_index.move | 168 |
| abstract_inverted_index.must | 10 |
| abstract_inverted_index.only | 84 |
| abstract_inverted_index.open | 106 |
| abstract_inverted_index.same | 122 |
| abstract_inverted_index.show | 163 |
| abstract_inverted_index.that | 90, 115, 164 |
| abstract_inverted_index.with | 97 |
| abstract_inverted_index.work | 46 |
| abstract_inverted_index.$\leq | 131 |
| abstract_inverted_index.Using | 152 |
| abstract_inverted_index.[25]. | 77 |
| abstract_inverted_index.case, | 81 |
| abstract_inverted_index.range | 65, 74 |
| abstract_inverted_index.robot | 182 |
| abstract_inverted_index.their | 160 |
| abstract_inverted_index.under | 51, 120 |
| abstract_inverted_index.while | 176 |
| abstract_inverted_index.and/or | 40 |
| abstract_inverted_index.formed | 85, 119 |
| abstract_inverted_index.latter | 80 |
| abstract_inverted_index.memory | 39, 60, 76, 95 |
| abstract_inverted_index.mobile | 8 |
| abstract_inverted_index.mutual | 144 |
| abstract_inverted_index.range, | 100 |
| abstract_inverted_index.range. | 44 |
| abstract_inverted_index.robots | 9, 20, 37, 57, 69 |
| abstract_inverted_index.shrunk | 88 |
| abstract_inverted_index.unable | 29 |
| abstract_inverted_index.Without | 94 |
| abstract_inverted_index.assumed | 23 |
| abstract_inverted_index.careful | 154 |
| abstract_inverted_index.cluster | 149, 166 |
| abstract_inverted_index.drawing | 177 |
| abstract_inverted_index.forming | 101 |
| abstract_inverted_index.initial | 128, 143 |
| abstract_inverted_index.limited | 42, 72, 98 |
| abstract_inverted_index.managed | 47 |
| abstract_inverted_index.natural | 53 |
| abstract_inverted_index.partial | 111 |
| abstract_inverted_index.pattern | 3, 14, 184 |
| abstract_inverted_index.provide | 109 |
| abstract_inverted_index.remains | 104 |
| abstract_inverted_index.robots' | 127 |
| abstract_inverted_index.robots, | 161 |
| abstract_inverted_index.showing | 114 |
| abstract_inverted_index.through | 173 |
| abstract_inverted_index.version | 89 |
| abstract_inverted_index.viewing | 43, 64, 73, 99 |
| abstract_inverted_index.whether | 36 |
| abstract_inverted_index.Previous | 45 |
| abstract_inverted_index.clusters | 158 |
| abstract_inverted_index.constant | 92 |
| abstract_inverted_index.diameter | 129 |
| abstract_inverted_index.dropping | 180 |
| abstract_inverted_index.exploits | 141 |
| abstract_inverted_index.patterns | 103 |
| abstract_inverted_index.problem, | 5 |
| abstract_inverted_index.problem. | 107 |
| abstract_inverted_index.protocol | 134 |
| abstract_inverted_index.solution | 112 |
| abstract_inverted_index.symmetry | 54, 123 |
| abstract_inverted_index.\subseteq | 16 |
| abstract_inverted_index.arbitrary | 2, 13, 102 |
| abstract_inverted_index.component | 175 |
| abstract_inverted_index.condition | 55, 124 |
| abstract_inverted_index.diameter. | 93 |
| abstract_inverted_index.formation | 4 |
| abstract_inverted_index.important | 33 |
| abstract_inverted_index.placement | 155 |
| abstract_inverted_index.typically | 22 |
| abstract_inverted_index.unlimited | 63 |
| abstract_inverted_index.component. | 151 |
| abstract_inverted_index.components | 139 |
| abstract_inverted_index.partitions | 135 |
| abstract_inverted_index.visibility | 145 |
| abstract_inverted_index.autonomous, | 7 |
| abstract_inverted_index.coordinate. | 185 |
| abstract_inverted_index.coordinated | 171 |
| abstract_inverted_index.distinction | 34 |
| abstract_inverted_index.communicate. | 31 |
| abstract_inverted_index.disoriented, | 27 |
| abstract_inverted_index.\mathbb{R}^2$. | 17 |
| abstract_inverted_index.(deterministic) | 19 |
| abstract_inverted_index.indistinguishable, | 26 |
| abstract_inverted_index.rotation-symmetric | 138 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |