The computational complexity of controller-environment co-design using library selection for distributed construction

Timmar, Mesam (2018) The computational complexity of controller-environment co-design using library selection for distributed construction. Masters thesis, Memorial University of Newfoundland.

[img] [English] PDF - Accepted Version
Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.

Download (2MB)


Creating specified structures through the coordinated efforts of teams of simple autonomous robots is a significant problem in distributed robotics. All previous ef- fort, both empirical and theoretical, has focused on the problems of designing either controllers or environments which, in tandem with given environments or controllers, built the specified structures. In this paper, we give the results of the first computa- tional and parameterized complexity analyses of the controller-environment co-design problem in the simple case where teams of finite-state robots are designed by select- ing controllers from a given library. We show that this problem cannot be solved efficiently in general or under a number of restrictions, and give the first restrictions under which this problem is efficiently solvable. We also consider two elaborations on this problem. First, we analyze the controller- environment co-design problem under a new architecture in which robots have a transient memory. Second, we give the first definitions of and derive computational complexity results for stigmergy-related parameters for the controller-environment co-design problem.

Item Type: Thesis (Masters)
Item ID: 13691
Additional Information: Includes bibliographical references (pages 84-89).
Keywords: Computational Complexity, Parameterized Complexity, Swarm Robotics, Controller-Environment Co-design, Distributed Construction
Department(s): Science, Faculty of > Computer Science
Date: October 2018
Date Type: Submission
Library of Congress Subject Heading: Robots--Control systems--Design; Self-organizing systems--Design; Swarm intelligence; Computational complexity

Actions (login required)

View Item View Item


Downloads per month over the past year

View more statistics