On Scalable Supervisory Control Of Multi-Agent Discrete-event Systems

In this paper we study centralized and distributed supervisory control problems of multiagent discrete-event systems which are composed of several groups of agents,within each group the agents have similar or identical state transition structures.Such system is used in situations where several entities(e.g.multiple machines in factories,robots in manufacturing cells,and AGVs in logistic systems)perform the same type of jobs,while their number can vary in time.For the above system,we study four aspects.Firstly,we employ the similar state transition structure to construct models for each group and based on the models investigate a scalable supervisor with full observation,where state sizes and computational process of the scalable supervisor are independent of the number of agents.This scalability allows the supervisor to remain invariant(no recomputation or reconfiguration needed)if and when there are agents removed due to failure or added for increasing productivity.The constant computational effort for synthesizing the scalable supervisor also makes our method promising for handling large-scale multi-agent systems.Moreover,based on the scalable supervisor we design scalable local controllers,one for each component agent,to establish a purely distributed control architecture.Moreover,based on the scalable supervisor we design scalable local controllers,one for each component agent.the local controllers we designed for individual agents have the same scalability feature,and are guaranteed to collectively achieve identical controlled behavior as the centralized supervisor does.Secondly,we extend the computation of scalable supervisors to the case of partial observation,where in addition to controllability,the observability property is needed to synthesize the supervisors.In this thesis,a centralized scalable supervisor is designed by using model structures of the system when some events cannot be observed.And it is proved that in the case of partial observation,the number of states and computational process of the supervisor will not change with the number of agents.In addition,based on the centralized scalable supervisor,we also design scalable local controller under partial observation.It is proved that the local controllers in the same group are the same,and the computational process and the number of states of the scalable local controllers are independent of the number of agents.We compare permissiveness of a monolithic supervisor with a scalable,template based,supervisor under partial observation.In addition,we investigate the conditions under which a scalable least restrictive supervisor based on the supremal relatively observable sublanguage on the template level is not more restrictive than the monolithic one.Moreover,we prove that all the given conditions can be checked with low computation.Thirdly,we investigate the symmetric properties and corresponding supervisory control problem of multi-agent discrete-event systems.Given a specification,we employ a symmetric mapping to calculate the supremal symmetric sublanguage of the specification,and prove that the supremal symmetric sublanguage of a decomposable language is also decomposable,and can thus be computed locally.After studying the one-level decomposability of the supremal symmetric sublanguage,2-level decomposability of the specification is further considered according to 2-level structure of the system.We propose a modular approach to construct the template supervisors based on a local computation of supremal symmetric sublanguages for the specification,and on the concept of 2-level conditional decomposability.It is proved that the local controllers of agents in the same group are similar,so they can be obtained from the symmetric mapping of a template supervisor.This method can effectively reduce computation costs when the system has a large number of agents.Finally,to reduce observation/communication cost caused by the number of events of the supervisor or local controllers that cause state changes,we propose an alternative localization algorithm that aims to compute local controllers of as few state-change events as possible.The localization algorithm designed in this thesis uses the state transition structure of a supervisor to check each state of the supervisor and its future states which are reached through one-step transition,and records the state-change events generated in the localize process with a new event set.After checking all possible state pairs,a corresponding local controller and a state-change event set can be obtained.We compare the state-change events of the local controllers obtained our proposed algorithm and those generated by a previously known localization algorithm by lots of tests and show that our proposed algorithm generally produces fewer state-change events than the previously known localization algorithm.In addition,it is proved that the time complexity of the algorithm is lower than that of the previous localization algorithm.Moreover,we prove that the problem of finding a local controller with minimum state-change events is NP-hard.