We study the computational complexity of collecting items inside a grid map with obstacles, using an agent that always slides to the maximal extend, until it is stopped by an obstacle. An agent could be, for example, a robot or a vehicle, while obstacles could be walls or other immovable objects, and items could be packages that need to be picked up.
This problem has very natural applications in robotics. The restricted type of motion of the agent naturally models movement on a frictionless surface, and movement of a robot with limited sensing capabilities and thus limited localization. For example, if a robot cannot determine the distance traveled once it starts moving, then it makes sense to keep moving until an obstacle is reached, even if the robot has a map of the environment.
With today’s technology it is possible to create sophisticated robots but, since the complexity and the costs of such robots are high, it is sometimes better to use simple inexpensive robots that can still solve relatively complex tasks. In fact, simple robots are quite common and usually built using simple sensors that have limited capabilities, but that are easy to use and are considerably cheaper than more sophisticated ones.
The computational complexity of numerous problems with movable objects has been extensively studied before. However, only a few of them have maximal sliding agents, and they usually do not have the goal of collecting items. We show that the problem of deciding if all the items can be collected by a maximal sliding agent can be solved efficiently when the agent is the only moving object in the map. However, we show that optimization problems such as determining the minimum number of moves required to collect all the items, and also variants in more complex environments are computationally intractable. Hence, for those problems it is better to focus on using heuristics than on finding optimal solutions.
| Identifer | oai:union.ndltd.org:UTAHS/oai:digitalcommons.usu.edu:etd-4706 |
| Date | 01 May 2014 |
| Creators | Tejada, Pedro J. |
| Publisher | DigitalCommons@USU |
| Source Sets | Utah State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | All Graduate Theses and Dissertations |
| Rights | Copyright for this work is held by the author. Transmission or reproduction of materials protected by copyright beyond that allowed by fair use requires the written permission of the copyright owners. Works not in the public domain cannot be commercially exploited without permission of the copyright owner. Responsibility for any use rests exclusively with the user. For more information contact Andrew Wesolek (andrew.wesolek@usu.edu). |
Page generated in 0.0023 seconds