Uniform Robot Relocation is Hard in only two Directions even without Obstacles

Uniform Robot Relocation is Hard in only two Directions even without Obstacles | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Uniform Robot Relocation is Hard in only two Directions even without Obstacles David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, and 2 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3762289/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 13 Dec, 2024 Read the published version in Natural Computing → Version 1 posted 7 You are reading this latest preprint version Abstract Given n robots contained within a square grid surrounded by four walls, we ask the question of whether it is possible to move a particular robot a to a specific grid location b by performing a sequence of global step operations in which all robots move one grid step in the same cardinal direction (if not blocked by a wall or other blocked robots). We show this problem is NP-complete when restricted to just two directions (south and west). This answers the simplest fundamental problem in uniform global unit tilt swarm robotics. We then consider a relaxed version of this problem in which the goal is to move a robot a to a specific row regardless of its horizontal placement. We show that if asking about the bottom-most row of the square grid, then this version of the problem is solvable in polynomial time. Finally, we discuss several areas for future research and open problems. Relocation Swarm Robot Motion Planning Row Relocation Tilt Model Global Uniform Signals Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 13 Dec, 2024 Read the published version in Natural Computing → Version 1 posted Reviews received at journal 20 Feb, 2024 Reviewers agreed at journal 09 Jan, 2024 Reviewers agreed at journal 21 Dec, 2023 Reviewers invited by journal 20 Dec, 2023 Editor assigned by journal 20 Dec, 2023 Submission checks completed at journal 19 Dec, 2023 First submitted to journal 16 Dec, 2023 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-3762289","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":261584856,"identity":"5a55d422-3579-46f5-b46b-c8f3bc279c9b","order_by":0,"name":"David Caballero","email":"","orcid":"","institution":"University of Texas Rio Grande Valley","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"David","middleName":"","lastName":"Caballero","suffix":""},{"id":261584857,"identity":"b6a05f51-0ca6-46fc-8e36-ff9363805ce8","order_by":1,"name":"Angel A. Cantu","email":"","orcid":"","institution":"Southwest Research Institute","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Angel","middleName":"A.","lastName":"Cantu","suffix":""},{"id":261584858,"identity":"d6c0392e-434e-4c04-a08e-04367cf880c7","order_by":2,"name":"Timothy Gomez","email":"","orcid":"","institution":"Massachusetts Institute of Technology","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Timothy","middleName":"","lastName":"Gomez","suffix":""},{"id":261584860,"identity":"52c7a981-2dde-4e47-b0a8-386c7eb698ec","order_by":3,"name":"Austin Luchsinger","email":"","orcid":"","institution":"University of Texas Austin","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Austin","middleName":"","lastName":"Luchsinger","suffix":""},{"id":261584862,"identity":"d96aac44-8609-4336-baaf-1bc0432f00a9","order_by":4,"name":"Robert Schweller","email":"","orcid":"","institution":"University of Texas Rio Grande Valley","correspondingAuthor":false,"submittingAuthor":false,"prefix":"","firstName":"Robert","middleName":"","lastName":"Schweller","suffix":""},{"id":261584866,"identity":"62f07b47-edf4-4052-a3ae-f863e92bf46b","order_by":5,"name":"Tim Wylie","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA70lEQVRIie3PMQrCMBSA4RcKOthSxwjiGTrp0MGrVBx6A1EQiQhxEbpWEE/gIoI4JgScqrOj4urQbi6Csbbi0trRIT8EHuF9kACoVP+YJg8i8UQY9NPrUrbQX4THBEkSAP5N4IsAogVIu1zpXKOdAOvUGbNoKUYtb2VB2BM5DzM2Fg9iQvh8K3D9dLOQf8wlW8ypgKYkwpAE472jGbQoeSwS8ihMEJHEnDAN5REh/3Kgrt4OLoTP9m7Nxxrjs6ObScreYX0eULtRm3ZFeB/aJjb5+Hzv2ZkkaaJD1Ulm7AD7tS8bAZjp3mdQqVQq1bsnLileukmRpIUAAAAASUVORK5CYII=","orcid":"","institution":"University of Texas Rio Grande Valley","correspondingAuthor":true,"submittingAuthor":false,"prefix":"","firstName":"Tim","middleName":"","lastName":"Wylie","suffix":""}],"badges":[],"createdAt":"2023-12-16 07:44:07","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-3762289/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-3762289/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s11047-024-10007-4","type":"published","date":"2024-12-13T15:56:57+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":71552427,"identity":"10f8831e-2805-4a6e-af29-fddcafe94d0f","added_by":"auto","created_at":"2024-12-16 16:06:00","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1530552,"visible":true,"origin":"","legend":"","description":"","filename":"2DRobotsJournalNACO24.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3762289/v1_covered_7c62bbfc-f95e-4c11-97a3-7e16c9728ed3.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Uniform Robot Relocation is Hard in only two Directions even without Obstacles","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"natural-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"naco","sideBox":"Learn more about [Natural Computing](http://link.springer.com/journal/11047)","snPcode":"11047","submissionUrl":"https://submission.nature.com/new-submission/11047/3","title":"Natural Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Relocation, Swarm Robot Motion Planning, Row Relocation, Tilt Model, Global Uniform Signals","lastPublishedDoi":"10.21203/rs.3.rs-3762289/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3762289/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eGiven \u003cem\u003e\u003cstrong\u003en\u003c/strong\u003e\u003c/em\u003e robots contained within a square grid surrounded by four walls, we ask the question of whether it is possible to move a particular robot \u003cem\u003e\u003cstrong\u003ea\u003c/strong\u003e\u003c/em\u003e to a specific grid location \u003cem\u003e\u003cstrong\u003eb\u003c/strong\u003e\u003c/em\u003e by performing a sequence of global \u003cem\u003estep\u003c/em\u003e operations in which all robots move one grid step in the same cardinal direction (if not blocked by a wall or other blocked robots). We show this problem is NP-complete when restricted to just two directions (south and west). This answers the simplest fundamental problem in uniform global unit tilt swarm robotics. We then consider a relaxed version of this problem in which the goal is to move a robot \u003cem\u003e\u003cstrong\u003ea\u003c/strong\u003e\u003c/em\u003e to a specific row regardless of its horizontal placement. We show that if asking about the bottom-most row of the square grid, then this version of the problem is solvable in polynomial time. Finally, we discuss several areas for future research and open problems.\u003c/p\u003e","manuscriptTitle":"Uniform Robot Relocation is Hard in only two Directions even without Obstacles","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2023-12-21 06:15:00","doi":"10.21203/rs.3.rs-3762289/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"editorInvitedReview","content":"","date":"2024-02-20T06:10:31+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"411292a5-2890-4254-b71c-84da6a528514","date":"2024-01-09T09:02:16+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"22d93603-4803-4ffe-aad5-d5ca1dba66ca","date":"2023-12-21T14:41:44+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2023-12-20T09:07:59+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2023-12-20T08:01:52+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2023-12-19T14:11:31+00:00","index":"","fulltext":""},{"type":"submitted","content":"Natural Computing","date":"2023-12-16T07:28:30+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"natural-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"naco","sideBox":"Learn more about [Natural Computing](http://link.springer.com/journal/11047)","snPcode":"11047","submissionUrl":"https://submission.nature.com/new-submission/11047/3","title":"Natural Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"a6b19f78-64ae-4a15-9b45-4245b30a6103","owner":[],"postedDate":"December 21st, 2023","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2024-12-16T16:00:42+00:00","versionOfRecord":{"articleIdentity":"rs-3762289","link":"https://doi.org/10.1007/s11047-024-10007-4","journal":{"identity":"natural-computing","isVorOnly":false,"title":"Natural Computing"},"publishedOn":"2024-12-13 15:56:57","publishedOnDateReadable":"December 13th, 2024"},"versionCreatedAt":"2023-12-21 06:15:00","video":"","vorDoi":"10.1007/s11047-024-10007-4","vorDoiUrl":"https://doi.org/10.1007/s11047-024-10007-4","workflowStages":[]},"version":"v1","identity":"rs-3762289","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3762289","identity":"rs-3762289","version":["v1"]},"buildId":"cBFmMYwuxLRRLfASyISRj","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}