Seminar: The Computational Complexity of Controller-Environment Co-design using Library Selection fo

Mesam Timmar
M.Sc. Candidate
Supervisor: Dr. Todd Wareham

The Computational Complexity of Controller-Environment Co-design using
Library Selection for Distributed Construction

Department of Computer Science
Thursday, October 4, 2018, 1:00 p.m., Room EN 2022


Abstract

Creating specified structures through the coordinated efforts of teams of simple autonomous robots is a very important problem in distributed robotics. All previous effort, 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 computational and parameterized complexity analyses of the controller- environment co-design problem in the simple case where teams of finite-state robots are designed by selecting 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 have given the first definitions of and derived computational complexity results for stigmergy-related parameters for this problem.

Contact

Department of Computer Science

230 Elizabeth Ave, St. John's, NL, CANADA, A1B 3X9

Postal Address: P.O. Box 4200, St. John's, NL, CANADA, A1C 5S7

Tel: (709) 864-8000