Efficient Algorithms for Coordinated Motion in Shared Spaces

dc.contributor.advisorMount, David Men_US
dc.contributor.authorDasler, Philipen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.description.abstractThe steady development of autonomous systems motivates a number of interesting algorithmic problems. These systems, such as self-driving cars, must contend with far more complex and dynamic environments than factory floor robots of the past. This dissertation seeks to identify optimization problems that are simple enough to analyze formally, yet realistic enough to contribute to the eventual design of systems extant in real-world, physical spaces. With that in mind, this work examines three problems in particular: automated vehicles and unregulated traffic crossings, a smart network for city-wide traffic flow, and an online organizational scheme for automated warehouses. First, the Traffic Crossing Problem is introduced, in which a set of n axis-aligned vehicles moving monotonically in the plane must reach their goal positions within a time limit and subject to a maximum speed limit. It is shown that this problem is NP-complete and efficient algorithms for two special cases are given. Next, motivated by a problem of computing a periodic schedule for traffic lights in an urban transportation network, the problem of Circulation with Modular Demands is introduced. A novel variant of the well-known minimum-cost circulation problem in directed networks, in this problem vertex demand values are taken from the integers modulo λ, for some integer λ≥2. This modular circulation problem is solvable in polynomial time when λ=2, but the problem is NP-hard when λ≥3. For this case, a polynomial time approximation algorithm is provided. Finally, a theoretical model for organizing portable storage units in a warehouse subject to an online sequence of access requests is proposed. Complicated by the unknown request frequencies of stored products, the warehouse must be arranged with care. Analogous to virtual-memory systems, the more popular and oft-requested an item is, the more efficient its retrieval should be. Two formulations are considered, dependent on the number of access points to which storage units must be brought, and algorithms that are O(1)-competitive with respect to an optimal algorithm are given. Additionally, in the case of a single access point, the solution herein is asymptotically optimal with respect to density.en_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pqcontrolledOperations researchen_US
dc.subject.pquncontrolledAutonomous Vehiclesen_US
dc.subject.pquncontrolledComputational Theoryen_US
dc.subject.pquncontrolledMotion Planningen_US
dc.subject.pquncontrolledNetwork flows and circulationsen_US
dc.titleEfficient Algorithms for Coordinated Motion in Shared Spacesen_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
1.74 MB
Adobe Portable Document Format