The system consists of collection of services, running on several of nodes. The workload generated by services may cause nodes overload, which negatively impacts the response time of services. The reconfiguration of the system incrementally transforms one system state to the other. The goal of the reconfiguration is to transform the system state into one, which all services meet their response time. Finding the appropriate reconfiguration that satisfies all timing requirements is the dynamic, preemptive scheduling problem.
Ramaekers, Zachary (University of Nebraska, Omaha) | Dasgupta, Raj (University of Nebraska, Omaha) | Ufimtsev, Vladimir (University of Nebraska, Omaha) | Hossain, S. G. M. (University of Nebraska, Lincoln) | Nelson, Carl (University of Nebraska, Lincoln)
We consider the problem of dynamic self-reconfiguration in a modular self-reconfigurable robot (MSR). Previous MSR self-reconfiguration approaches search for new configurations only within the modules of the MSR that needs reconfiguration. In contrast, we describe a technique where an MSR that needs to reconfigure communicates with other MSRs in its vicinity to determine if modules can be shared from other MSRs, and then determines the best possible configuration among the combined set of modules. We model the MSR self-reconfiguration problem as a coalition structure generation problem within a coalition game theoretic framework. We formulate the coalition structure generation problem as a planning problem in the presence of uncertainty and propose an MDP-based algorithm to solve it. We have implemented our algorithm within an MSR called ModRED that is simulated on the Webots simulation platform. Our results show that using our self-reconfiguration algorithm, when an MSR needs to reconfigure, a new configuration that is within 5-7% of the globally optimal configuration can be determined. We have also shown that our algorithm performs comparably with another existing algorithm for determining optimal coalition structure.
We extend Reiter's general theory of model-based diagnosis [Reiter, 19871 to a theory of reconfiguration. The generality of Reiter's theory readily supports an extension in which the problem of reconfiguration is viewed as a close analogue of the problem of diagnosis. Using a reconfiguration predicate rcfg analogous to the abnormality predicate ab, we formulate a strategy for reconfiguration by transforming that for diagnosis. A benefit of this approach is that algorithms for diagnosis can be exploited as algorithms for reconfiguration, thereby promoting an integrated approach to fault detection, identification, and reconfiguration.