Approach of Agents with Restricted Fuel Tanks

Approach of Agents with Restricted Fuel Tanks | 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 Approach of Agents with Restricted Fuel Tanks Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, Grzegorz Stachowiak This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8490542/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 8 You are reading this latest preprint version Abstract Two mobile agents, modeled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct points, called their bases, at distance at most $D$, and wakes them up at possibly different times. Each of the agents has a fuel tank that allows them to traverse a trajectory of length $D$, and can be replenished at the base of the agent. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach. Our goal is to design approach algorithms with optimal time complexity. We consider two independent {\em coherence assumptions}.One of them is {\em time coherence}, i.e., agents start simultaneously, and the other is {\em orientation coherence}: agents have compatible compasses, showing the same North direction. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time $O(D^2)$ and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time $O(D^2\sqrt{D})$ and we prove that this order of magnitude cannot be improved. Our main technical contributions are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal. mobile agent approach rendezvous plane restricted energy Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Reviews received at journal 06 May, 2026 Reviewers agreed at journal 01 Mar, 2026 Reviewers agreed at journal 27 Feb, 2026 Reviewers agreed at journal 06 Feb, 2026 Reviewers invited by journal 05 Feb, 2026 Editor assigned by journal 05 Feb, 2026 Submission checks completed at journal 02 Jan, 2026 First submitted to journal 31 Dec, 2025 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-8490542","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":587675571,"identity":"841c14b1-7b6d-4c63-89f7-4d7b3c39f043","order_by":0,"name":"Adam Ganczorz","email":"","orcid":"","institution":"University of Wrocław","correspondingAuthor":false,"prefix":"","firstName":"Adam","middleName":"","lastName":"Ganczorz","suffix":""},{"id":587675572,"identity":"dcae5299-e95d-495e-9441-e4b986af2c1a","order_by":1,"name":"Tomasz Jurdzinski","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAwElEQVRIiWNgGAWjYFCCA4wPwDQzTICdgAYehgPMBqhamHEqhmlhYJNAFSKkxZ7xjFnFjz8MidvZGdikKyrsGMwJ23LG7GZvG0PizmYGNskzZ5IZLJuJ0HKbsYEhccNhBrabjW0HGAwOE6GlmOEPqVqYGdhI0nLgWLFkb5uE8YbDjO0/G84k8xD0C/uMwxs//PhjI7vh/OHDhg0VdnLm7A0E9EgcAJNAzAhWymNAQAMDAz+6mYS1jIJRMApGwUgDADuzPNHyfm7gAAAAAElFTkSuQmCC","orcid":"","institution":"University of Wrocław","correspondingAuthor":true,"prefix":"","firstName":"Tomasz","middleName":"","lastName":"Jurdzinski","suffix":""},{"id":587675573,"identity":"c459a90c-3323-4fc9-9727-5a9ab0373ef6","order_by":2,"name":"Andrzej Pelc","email":"","orcid":"","institution":"Université du Québec en Outaouais","correspondingAuthor":false,"prefix":"","firstName":"Andrzej","middleName":"","lastName":"Pelc","suffix":""},{"id":587675574,"identity":"f7853500-b76f-4632-a3b4-bdca15903419","order_by":3,"name":"Grzegorz Stachowiak","email":"","orcid":"","institution":"University of Wrocław","correspondingAuthor":false,"prefix":"","firstName":"Grzegorz","middleName":"","lastName":"Stachowiak","suffix":""}],"badges":[],"createdAt":"2025-12-31 14:38:53","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8490542/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8490542/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":102270680,"identity":"bc303b75-c7fd-4cec-9b95-cc338ba7e3ec","added_by":"auto","created_at":"2026-02-10 04:10:28","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":468565,"visible":true,"origin":"","legend":"","description":"","filename":"submissionfiles.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8490542/v1_covered_38c163e1-d176-49fd-bebc-5a191efa042d.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Approach of Agents with Restricted Fuel Tanks","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"distributed-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"dist","sideBox":"Learn more about [Distributed Computing](http://link.springer.com/journal/446)","snPcode":"446","submissionUrl":"https://submission.nature.com/new-submission/446/3","title":"Distributed Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"mobile agent, approach, rendezvous, plane, restricted energy","lastPublishedDoi":"10.21203/rs.3.rs-8490542/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8490542/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eTwo mobile agents, modeled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct points, called their bases, at distance at most $D$, and wakes them up at possibly different times. Each of the agents has a fuel tank that allows them to traverse a trajectory of length $D$, and can be replenished at the base of the agent. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach. Our goal is to design approach algorithms with optimal time complexity. We consider two independent {\\em coherence assumptions}.One of them is {\\em time coherence}, i.e., agents start simultaneously, and the other is {\\em orientation coherence}: agents have compatible compasses, showing the same North direction. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time $O(D^2)$ and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time $O(D^2\\sqrt{D})$ and we prove that this order of magnitude cannot be improved. Our main technical contributions are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal.\u003c/p\u003e","manuscriptTitle":"Approach of Agents with Restricted Fuel Tanks","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-02-10 04:09:53","doi":"10.21203/rs.3.rs-8490542/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"editorInvitedReview","content":"","date":"2026-05-06T14:59:10+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"107970016783999789737139320645643081628","date":"2026-03-01T20:03:11+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"209626743709992958790084669044335060966","date":"2026-02-28T01:42:55+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"269924369637269145206506027484690879772","date":"2026-02-06T08:58:05+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2026-02-06T04:23:35+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-02-06T04:20:15+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2026-01-02T13:00:32+00:00","index":"","fulltext":""},{"type":"submitted","content":"Distributed Computing","date":"2025-12-31T14:32:47+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"distributed-computing","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"dist","sideBox":"Learn more about [Distributed Computing](http://link.springer.com/journal/446)","snPcode":"446","submissionUrl":"https://submission.nature.com/new-submission/446/3","title":"Distributed Computing","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"df0126b0-2612-4537-8831-1b01d1e248dc","owner":[],"postedDate":"February 10th, 2026","published":true,"recentEditorialEvents":[{"type":"editorInvitedReview","content":"","date":"2026-05-06T14:59:10+00:00","index":17,"fulltext":""}],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-02-10T04:09:53+00:00","versionOfRecord":[],"versionCreatedAt":"2026-02-10 04:09:53","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8490542","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8490542","identity":"rs-8490542","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}