The doctoral project summarised in this paper proposes a modular software architecture for the scheduling of multi-robot system (MRS) missions with complex functional and nonfunctional requirements. The new architecture comprises separate components for maintaining specifications of the mission tasks, environment and robot capabilities, for allocating the required tasks to the available robots, for scheduling the tasks executed by each robot, etc.-all of these providing guarantees that the mission requirements will be achieved. Each such component and its elements can be flexibly instantiated using either ofthe-shelf software (e.g., constraint solvers or model checkers) or purpose-built software modules. To show the feasibility of the proposed MRS mission-scheduling architecture, we instantiated it using Alloy Analyzer to allocate mission tasks and the PRISM probabilistic model checker to generate individual robot plans for a hospital case study involving the scheduling of MRS missions that required cleaning, sanitising and moving medical equipment in multiple hospital rooms.
Research in robotic systems has increased exponentially over the last 50 years [
Developing a software solution for this complex, multifaceted problem requires a modular, lfexible software architecture. The doctoral project described in this paper aims to develop such an architecture. Our planned architecture comprises components for handling the required inputs (including, for instance, information about the available robots and the conflicting optimisation requirements of their missions) provided in multiple domain-specific languages. Additionally, it includes model-to-model transformations to convert these inputs into models that can be supplied to constraint solvers, model checkers and other reasoning engines to allow the allocation of tasks to individual robots, robot-level planning, etc. Furthermore, we envisage that, through the use of formal techniques, our solution will provide guarantees that the MRS will achieve its strict functional and nonfunctional requirements.
Most research on the deployment of robots in applications with strict requirements focuses on
the planning problem [
Formal techniques have been used to guarantee robot mission compliance with safety
properties both at the static planning (ofline) [
Thus, the research on mission-scheduling architectures for MRS with complex functional and nonfunctional requirements is still in the early days. Monolithic architectures have been studied, with only a few considering task allocation as part of the process. The variety of challenges that need to be solved (uncertainty in the environment and robots, allocation of tasks, scheduling of tasks, planning, etc.) suggest that a monolithic MRS lacks flexibility to incorporate all these concerns. Therefore, the adoption of a modular architecture for the deployment of complex MRS is explored in this doctoral project.
As shown in Figure 1, our MRS mission-scheduling architecture comprises five components: 1) Model repository. A first research question (RQ1) for the project is how to specify the system. To this end, we use a Model repository with four sub-components. First, a Task specification describes the types of tasks that can be used to assemble MRS missions, with their hierarchical composition, probabilities of success, durations, etc. A domain specific language (DSL). Second, a World model expressed in a suitable DSL is used to capture the relevant characteristics of the environment in which the MRS missions need to be performed. Third, a Robot specification provides information about the capabilities, locations, etc. of the robots that could be used to perform missions. Finally, a Mission specification describes what tasks must be accomplished, at which locations and with what reliability, performance and other nonfunctional constraints.
speci cation ) ( p B a Probabilistic rto ...
dA model checker, etc.
Constraint solver, etc.
Tasmkaanlalogceartor ...
Monitor & Analyse
Plan Manager Execute
Task allocation models Robot plans
hhactuatorsii hhsensorsii
Optimiser manager
Multiobjective optimiser
Robot
plan
repository
provided interface
required interface
component
dependency
port
2) Task allocator. For the allocation of tasks to robots (RQ2), Adaptor (A) obtains the four
specifications from the Model repository, and transforms them into a model that can be supplied
to one or several reasoning engines (e.g., Constraint solver modules) that a Task allocator manager
uses to create multiple feasible Task allocation models that partition the mission tasks to (a subset
of) the available robots. Each of these task allocations is guaranteed to enable the satisfaction
of all the functional requirements1 of the MRS mission provided that the tasks assigned to each
robot are appropriately scheduled.
3) Task scheduler. Adaptor (B) reads each task allocation model, and the necessary system
information from the model repository (for example, constraints over the tasks) and creates
models and formal specifications readable by scheduling engines such as probabilistic model
checkers. A Task scheduler manager (RQ3) coordinates the models, specifications and scheduling
engines to create feasible Robot plans that define what each robot needs to do and when—and
that are guaranteed to satisfy the functional and nonfunctional requirements of the MRS mission.
This component captures constraints via the model or the logic specifications. Such constrains
may include, for example, the requirement that a task T1 is done immediately after a task T2, or
1Functional requirements refer to the behaviour of the system, how it should "behave", e.g, a) ordered tasks
must be done in the specific order they appear in the compound task; b) compound tasks have two or more tasks
without including themselves; or c) the tasks must be assign to robots that have the capability to do the tasks.
that a task T3 must be performed by two robots at the same time.
4) Optimiser. The Optimiser manager selects the feasible paths that are optimal, i.e., that
minimise or maximise the reliability, performance or utility of the mission, as required in
the Mission specification . This can be done through Multiple-objective optimisation techniques.
The parameters to optimise can be computed using diferent reasoning engines (RQ4), e.g.,
probabilistic model checking can be used to compute the probability of mission success, and
a purpose-built mission time estimator can be used to establish the mission completion time
or the number of robots deployed. The Optimiser manager can also request the Task allocator
and/or the Task scheduler to generate additional feasible allocations of tasks models, or robot
plans if no optimal solution is found. the optimiser also deals with situations where the task
allocator generates no solution that can meet the non-functional requirements The optimisation
can also be carried out within the allocation and scheduling components, e.g. by allocating the
tasks to robots depending on the shortest distance, or by computing only the schedules that
minimise the total completion time.
5) Deployment and Adaptation Manager. At run-time, the system follows a MAPE-K
(Monitor-Analyze-Plan-Execute over a shared Knowledge) loop [
A first version of the MRS mission-scheduling architecture was implemented [
The world is modelled as a (complete) weighted graph with vertices corresponding to each of the rooms and initial robot positions, and weighted edges between these (where the weights represent travelling distances). Two cleaner robots (r1, r2) and two pick-and-place robots (r3, r4) are available. A total of 672 feasible allocation models where computed by Alloy Analyzer. Markov decision processs models were created for each of these allocations by the task scheduler, and appropriate robot plans were synthesised by finding the policy that minimizes the travelling cost. Details on the case study and results are available at https://git.io/Js1Yj to conserve space.
The Deployment & adaptation manager component of our architecture is under development. A MRS mission-scheduling architecture based on the separation of concerns was proposed. Preliminary results generating the plans for a group of heterogeneous robots in a hospital scenario show the viability of the approach. As multiple studies consider part of the MRS scheduling problem (complex nonfunctional requirements, uncertainty, planning, etc.), this modular architecture allows the adoption of a wide range of of-the-shelf software components, combined into a robust and flexible MRS scheduling toolset. This doctoral project strives to build and evaluate this toolset. A further evaluation considering multiple scenarios and a test bed varying the number of robots, tasks, and rooms is planned to test feasibility and scalability.