-
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document -
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document -
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
Description
In several scenarios in which new robots and tasks are added to a network of already deployed, interchangeable robots, a trade-off arises in seeking to minimize cost to execute the tasks and the level of disruption to the system, This paper considers a navigation-oriented variant of this problem and proposes a parameterizable method to adjust the optimization criterion: from minimizing global travel time (or energy, or distance), to minimizing interruption (i.e., obtaining the fewest number of robot reassignments), and mixtures in-between. Paths are computed by task-allocation formulation in which destination locations of newly deployed robots are added as tasks to an existing allocation. We adapt the graph matching variant of the Hungarian algorithm—originally designed to solve the optimal assignment problem in complete graphs—to construct routing paths by showing that there is a three-dimensional spatial interpretation of the Hungarian bipartite graph. When new agent-task pairs are inserted, the assignment is globally reallocated in an incremental fashion so it requires only linear time when the robots’ traversal options have bounded degree. The algorithm is studied systematically in simulation and also validated with physical robots.