A Research On Mechanisms And Algorithms For Supporting Schedule Maintenance Of Multi-Robot Systems

A multi-robot system is a robotic system consisting of multiple robots that work together to accomplish one or more tasks.It typically runs in a dynamic environment and therefore needs to adjust the composition and behavior of the system based on changes in the environment and user requirements.Our research focuses on a schedule-based method of organising the behaviour of a multi-robot system,in which each robot possesses a schedule to indicate the execution order of the robot's tasks.Due to the persistent changes in the environment and user requirements,the original execution conditions of the multi-robot schedules may be invalidated,and the various performance indicators of the schedules may be lowered,which may hinder the normal execution of the schedules.Therefore,a multi-robot system is expected to be able to maintain its schedules,by continuously adjusting the schedules in response to the change of the execution environment,so that the various performance indicators of the schedule meet the expected requirements or are improved.The schedule maintenance of multi-robot system in open environment faces the following challenges:(1)Consistency of the schedule: Under environmental changes,the multi-robot system may need to dynamically adapt the original set of tasks and the constraints among tasks,which may result in inconsistencies in the schedule—that is,there exist two or more tasks,whose positions in the multi-robot schedules do not meet the constraints between tasks,which hinders the normal execution of the schedules.Hence,the multi-robot system needs to persistently adjust the schedules in order to eliminate the inconsistencies,thereby ensuring the normal execution of the schedules.(2)Feasibility of the schedule: The resource requirements of each task in the schedule,the available resources in the environment,and the dynamic changes of the two,may cause the resource requirements of some tasks to be unsatisfied – that is,not feasible.The completion rate of tasks assigned to the multi-robot system may be reduced as a result.Therefore,the multi-robot system needs to continuously adjust the schedule according to the situation that the resource requirements of tasks are satisfied,thereby satisfying the resource requirements of as many tasks as possible.In view of the above problems,our research focuses on “schedule model”,“schedule consistency maintenance mechanism”,“schedule feasibility maintenance mechanism” and other aspects,and obtains the following results.1.A model for multi-robot scheduleThis model specifies the features of the schedule of a multi-robot system from the following perspectives: execution and resource consumption.From the execution perspective,the model defines:(1)the composition of multi-robot schedule;(2)the factors that constrains the execution of schedules(collectively called “task configuration”)and the dynamic change of these factors;(3)the operations for dynamically adapting the schedules,which are used to describe schedule maintenance mechanisms.From the resource consumption perspective,this model defines:(1)resource demands of schedules;(2)cost(i.e.,amount of consumed resources)of schedule execution.Based on the defined concepts,the model specifies the following conditions which may hinder the normal execution of schedules:(1)deadlocks within multi-robot schedule;(2)unsatisfied resource demands of tasks.These conditions are used to introduce the main problems faced by schedule maintenance mechanisms.The model defines basic concepts related to multi-robot schedule,and a preliminary analysis on the concerned issues,providing a basis for further researches.2.A mechanism for maintaining consistency of multi-robot schedule based on market-based task reallocation,which eliminates the inconsistency between schedule and task configurationWe present the mechanism for maintaining consistency of multi-robot schedules in order to deal with the inconsistencies in the multi-robot schedule(mainly reflected in the deadlock between tasks)caused by the dynamic adaptation of task configuration in response to environmental changes.The design of this mechanism includes following aspects:(1)Define the reachability between tasks based on the concept of task configuration and schedules.The reachability can be used to calculate the allowable range of positions of tasks in the multi-robot schedule.Present a criterion for verifying the consistency of tasks in schedules.(2)Present the algorithm which detects inconsistencies in schedules based on the criterion.(3)Present an algorithm for eliminating inconsistencies based on the conception of market-based task reallocation.The same task reallocation algorithm is also periodically invoked to lower the cost of schedules in order to deal with the negative effects of consistency maintenance on the performance of the schedules.We theoretically prove that the consistency maintenance mechanism is able to eliminate all inconsistencies in the schedules through finite iterations.We conduct experiments to validate the effectiveness of the consistency maintenance mechanism and the capability of periodic invocation of task reallocation algorithm in persistently reducing cost of multi-robot schedule.3.A mechanism for maintaining feasibility based on inter-robot resource delivery,which improves the ratio of tasks whose resource demands are satisfiedIn a situation where tasks have dynamic resource demands,the task configuration is dynamically changing,and the resources in the environment are limited,some tasks may fail to perform because their resource demands cannot be satisfied.In order to deal with such situation,we present a mechanism for maintaining the feasibly of the multi-robot schedule,which persistently improve the ratio of tasks whose resource demands are satisfied by the residual resources of the robots executing them,based on the conception of inter-robot resource delivery.The design of this mechanism includes following aspects:(1)Present an algorithm for maintaining feasibility of the multi-robot schedule,by inserting tasks for transferring resources from the robots with redundant resources to the robots in urgent need of resources.(2)Present an algorithm for maintaining cost-efficiency of the multi-robot schedule,based on the conception of market-based task reallocation,in order to deal with the negative effects of feasibility maintenance algorithm on the cost-efficiency of the schedule.This algorithm explicitly considers the influence of feasibility maintenance algorithm in order to prevent conflicts between the objectives of both algorithms.We theoretically prove that the feasibility maintenance mechanism:(1)will not introduce new inconsistencies into the multi-robot schedule,therefore doesn't conflict with consistency maintenance mechanism;(2)monotonically improve all schedules in the multi-robot system,which means it prevents the situation in which the feasibility of one schedule is improved at the expense of that of another schedule.We conduct experiments to validate that:(1)the feasibility maintenance algorithm can effectively improve the feasibility of entire multi-robot schedule;(2)the cost-efficiency maintenance algorithm can be seamlessly integrated with the feasibility maintenance algorithm in order to achieve certain synergetic effectiveness in maintaining cost-efficiency without causing conflicts.