Robots in Retirement Homes: Applying Off-the-Shelf Planning and Scheduling to a Team of Assistive Robots (Extended Abstract)

1 Introduction

The aging of global populations has had, and will continue to have, profound impact on our society [United Nations, 2002] with one particular challenge being the physical, cognitive, and psychological welfare and well-being of the elderly. Without an increase in the number of caregivers, the growth of the older population will lead to a strain on existing personnel to meet these needs. To address the lack of human resources, human-robot interaction (HRI) and robot companionship have been proposed and shown to have positive results on the human psychological state [Banks et al., 2008].

Our long-term project is the deployment of intelligent mobile robots in retirement homes to engage residents in stimulating recreational activities [Booth et al., 2016; Louie et al., 2014a; 2014b; 2015; Li et al., 2016; Mohamed and Nejat, 2016]. We have designed the robot, Tangy, to: 1) navigate using a laser range finder and 3D depth sensors, 2) detect users with 2D cameras, and 3) interact with users through speech, gestures, and a touch screen. While the implementation of the robot behaviors addresses robotics challenges (e.g., sensing, HRI, person and activity recognition), herein we focus on the planning and scheduling of the daily activities of multiple socially assistive robots such as Tangy. These plans and schedules are to be generated prior to the start of a day and executed by the team of robots during the day.

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Tran et al., 2017].

This paper studies the modeling and solving of a particular application. Such case studies serve as valuable feedback for researchers focusing on the theory and algorithms which form the core of planning and scheduling research.

The main contributions of this work are:

• Three modeling approaches for a complex multi-robot HRI problem using two different solving technologies: Planning Domain Definition Language (PDDL) and Constraint Programming (CP);
• One of the first applications of CP to a multi-robot planning and scheduling problem;
• The development of a CP-based decomposition that outperforms the other tested methodologies.

2 ProblemDefinition

We need to create a daily schedule for a team of robots in a retirement home environment. In this section, the main elements of the proposed problem are defined. The parameters and constraints were obtained from meetings with directors, healthcare professionals, and residents from Toronto area retirement homes [Louie et al., 2014a; 2015].

2.1 The Retirement Home Environment

The retirement home is discretized into a set of locations, L, representing different rooms in the environment with a known distance between any two locations l and m, denoted as dlm.

For a set of users, U, each user, ui ∈ U, has a personal profile that specifies a schedule, including his/her location and availability throughout the day. The user profile also represents preferences specifying that the user, u, wishes to participate in between att minu and att maxu multi-user HRI activities (Bingo games).

We are also given a set of robots, R. Each robot, ri ∈ R, starts the day at a charging station and is capable of moving in the retirement home environment at a fixed speed, vi. The robot facilitates the HRI activities by traveling to the appropriate location and interacting with the user(s) for the required amount of time. While the robot is traveling and performing activities, it consumes battery power at a rate dependent on the task. The battery level, bli of a robot, ri, must stay between bl mini ≤ bli ≤ bl maxi. During the day, a robot may need to travel to and recharge at a charging station.

The HRI activities are telepresence sessions and Bingo games. A set of telepresence sessions, S, represent the singleuser activities that are required to be scheduled during the day. Each telepresence session, y ∈ S, is associated with a user, u, a duration, dury, and a set of valid time intervals when it can occur. A set of Bingo games, G, represents the multi-user activities, optional tasks that add value to the daily schedule for users. A Bingo game, g ∈ G, is characterized by its location, the duration of the game durg, and a set of valid time intervals when it can be played. For each Bingo game, g, the number of participants must be between three and ten. The participating users must be available during the time of the Bingo game and each player must be reminded of the game by a robot 15 to 120 minutes before it begins.

2.2 Input and Goal

The inputs to the problem are the sets of locations, L; users, U (with their profiles); charging stations, K ⊂ L; available robots, R (with their initial locations, velocity, and battery level and consumption details); the requested telepresence sessions, S; and possible Bingo games, G. The goal is to create a plan of robot tasks in which all the requested telepresence sessions are scheduled and the requested Bingo games and reminders are scheduled, if possible, given that user attendance preferences have to be satisfied. Furthermore, the participating users must be chosen for each Bingo game as part of the problem solving. At the end of the day, all robots must be at a location with a charging station.

As a multi-objective optimization problem, we want to: 1) perform as many Bingo games as possible, 2) have as many users playing Bingo as possible, 3) provide reminders as close as possible to the game times, and 4) expend as little battery power as possible. The objective function considered is:

Here, B is the number of Bingo games played and P is the total number of participants across all Bingo games. The values of δ and ϵ represent the sum of time between all reminders and their corresponding Bingo games and the total energy usage of all robots, respectively.

3 SolutionMethods

We present three different approaches to solving the robot task scheduling problem: PDDL-based planning, constraintbased scheduling, and a constraint-based scheduling decomposition. In the interest of space, we only present partial models. For the complete models, and five alternative PDDL models that do not perform as well as the one presented here, see our full paper [Tran et al., 2017].

Planning and scheduling differ in the abstractions used to model tasks in each paradigm. In the former, it is sufficient to model tasks by utilizing operators, which dictate how the state of the world may be changed. An operator is instantiated to create a ground action and the planner decides how many times to instantiate each operator and their sequence to reach a goal state. For example, to charge the battery on a robot, the planner has access to a battery recharging operator that can be executed by any robot as many times as necessary.

In contrast, typical scheduling solvers require that every potential task is modeled as an optional task [Laborie, 2003]. This approach allows one to model a task but not necessarily execute it. For example, the maximum number of charging tasks must be known prior to scheduling in order to know how many optional tasks to create. The same must be done for the reminders and Bingo games since it is not known a priori which users are assigned to a Bingo game or whether a game will be played or not. The bounds introduced for the scheduling models provide the schedulers with additional information not available to the planners.

3.1 PDDL-Based Planning

The first methodology uses PDDL [Ghallab et al., 1998], specifically PDDL2.2 with processes from PDDL+. The main classes of the model are: Location, ChargingStation, Robot, User, TelepresenceSession, BingoGame, and Global.

A robot can perform seven operations: move, recharge, remind, do telepresence, play Bingo, interact, and skip Bingo. Other than recharge and do telepresense, all other operators are used to model Bingo games. The move operator moves a robot from one location to another to seek users for reminders and to facilitate a Bingo game in the games room, while having a duration and energy consumption based on the distance.

Each Bingo game has the properties dur, to represent duration; not done and done, to represent whether the game has been performed; and timed-initial literals must be done during, to represent the timewindows inwhich the task can be performed. In addition to the properties of the games introduced in the problem description, we have added the fluents p num and p cur to control the number of users reminded by the robots and the number of users playing the game, as well as delivery time to control the time at which each user is reminded about the game.

In the remind operator, a robot must be ready to perform the task and the user has to be available at the same location as the robot. Since the users are moving in the environment, we model their location over time and require that the robot and user be in the same location then the reminder occurs. The time of the reminder is recorded in the fluent delivery time, which becomes a condition for the Bingo operators.

Modeling the time between the delivery of a reminder and its associated Bingo game is done by processes [Fox and Long, 2006]. A process (called clock ticker) models an exogenous activity that is triggered for as long as a condition holds (in this case the fluent can start clock), regardless of the action selection process. This mechanism allows us to increment the fluent current time one minute at a time, simulating the passage of time in discrete one-minute intervals.

In order to facilitate a game after the reminders, a robot has to first start the play Bingo action, then it has to concurrently perform the interact action with each participant. The play Bingo action can only finish when the robot has performed the interact action with all assigned players. The interact action is used to ensure that users are participating in the Bingo game for the duration of the game.

In the scenario where a Bingo game is not played, the action skip Bingo is performed to ensure that the Bingo activity is considered done for the goal state.

3.2 Global-CP

The second methodology uses CP and is called Global-CP. Each robot task is represented by an interval variable [Laborie, 2009], aj, defined by a start time, end time, and size, which refers to the battery power required to perform the task. Other than the telepresence sessions, these tasks are optional; i.e., presenceOf(aj) can be equal to 1 (performed) or 0 (not performed). Furthermore, each HRI-related task has a number of clone tasks, which are required to model the alternative robots that can complete the tasks. For each task j, there are |R| additional tasks indexed by i and denoted by αij .

The scheduler must decide which robot executes each of the executed tasks via the clone tasks. We link these tasks with an alternative constraint, alternative(aj, {a1j, . . . , a|R|j}) that ensures that if a task aj is present in the schedule, then exactly one other task from the set of tasks {a1j, . . . , a|R|j} is also present. Thus, if a task aj is scheduled, then an appropriate task aij is also present and this task corresponds with robot i which is assigned to execute the task.

To ensure that robots perform at most one task at a time, a cumulative function, rci is used for each robot i. Cumulative functions are piecewise functions over time with discrete value changes made at the start and end times of interval variables [Laborie, 2009]. We use a pulse effect for every task aij on cumulative function rci, which increases (decreases) the cumulative function by one at the start (end) of the interval variable. By restricting rci ≤ 1, we ensure that each robot does not perform multiple tasks in parallel.

Similarly, users can only be active in one HRI activity at a time. A cumulative function, ucu, is used, where all tasks pertaining to a user u must also exhibit a pulse effect. Additionally, these tasks must be restricted to only occur during times when the user is available. We make use of calendars available in CP Optimizer to restrict the start times of a task.

One complication of our problem domain is the representation of robot and user movement within the environment. Typically, travel times are represented as minimum separation requirements between two tasks, where the separation must be greater than or equal to the time needed to travel between locations [Pesant et al., 1998]. However, because the robots must interact with users and the users themselves move within the environment, the exact location of and therefore, the travel time before, an interaction depends on the time that the action takes place. Our approach is to create additional tasks for each reminder based on the possible locations for a reminder for a particular user throughout the day. It is then possible to treat travel times as sequence-dependent setup times as is standard in scheduling (e.g., [Tran et al., 2016]) to ensure that the robot is given sufficient time for travel.

To model the interaction of users in Bingo games, we create an additional set of |U| optional interval variables for each Bingo game. This set is used to ensure that a user who is assigned to a Bingo game will participate in the game at the appropriate time (similar to the interact operator from the PDDL model). A user who has not been reminded of a Bingo game will not participate in the game. However, if a user was reminded, then the scheduler must ensure that the corresponding user-Bingo game interaction task is performed. This task will have a pulse effect on the relevant user's cumulative function, ucu, similar to how other interval variables affect the availability of a robot. Additionally, we constrain the start time of executed reminder tasks to be between 15 and 120 minutes before the appropriate Bingo game task by bounding the separation between the two tasks.

3.3 CP-Based Decomposition

Smith et al. [2000] noted that one of the weaknesses of scheduling is the inability to adequately handle environments with cascading effects. An action with a cascading effect changes the system state and leads to requirements for one or more other actions. For example, if a user is to play a Bingo game, he or she must be reminded of the game. However, if a user is not participating in a Bingo game, the reminder should not take place. Due to such dependencies, the scheduling model becomes very large since we create alternative interval variables for every possible action. We propose a decomposition of the CP model, Decomposed-CP, that attempts to improve upon Global-CP and better handle cascading effects.

The decomposition is comprised of two stages: a master problem and a sub-problem. The master problem is the Global-CP model, but with a simplified objective function: minf = |U| - P. The master problem solution is feasible for the complete problem, however, it may be of poor quality since most of the objective function is ignored.

The solution of the master problem gives an assignment of users to Bingo games that is used in the sub-problem. Only games that were played in the master problem are available to be played in the sub-problem with the same players, but without fixed start-times. The upper bound for the number of charging tasks per robot is set to the total number of charging tasks across all robots in the master solution. We choose this upper bound to allow for some flexibility in changing how often a recharge occurs, while guaranteeing that a feasible schedule exists. The objective function of the sub-problem is the original objective function (Equation 1). Note that in this decomposition, the optimal assignment of games and the number of recharges might not be optimal for the original problem.

When using the Decomposed-CP model, we set a time limit for the master problem that is half the total time limit. We switch to solving the sub-problem when either the master problem has been solved to optimality or when the time-limit is reached; whichever occurs first.

4 Empirical Evaluation

We consider a retirement home environment in which residents undertake several activities in different locations during the day. We assume that each user has seven one-hour noninterruptible activities (e.g., physiotherapy, doctor's appointment, family visit, nap, meals). Other, interruptible, activities (e.g., walk in the garden, read in a common area) allow robot interactions, but in various locations. At least one interruptible activity is assumed for each user. We analyze the proposed models for five full-day scenarios representing the requirements of the retirement home, but with a varying number of users, robots, and HRI activities (see Table 1). User schedules were obtained from our collaborating retirement homes.

We run each model on the five scenarios using a 64-bit Ubuntu Linux machine with 12 GB of memory and a onehour time limit. The OPTIC planner [Benton et al., 2012] is used to solve the PDDL planning model. The CP models are solved using IBM ILOG CPLEX CP Optimizer 12.6.2. We measure runtime, number of participants in Bingo games, and the objective function as performance metrics.

The performance of each methodology is presented in Table 2. The PDDL solver always finds a feasible solution, but these plans are low quality as they do not contain any Bingo games except for scenario 1. OPTIC struggles to improve upon the initial solution. In contrast, Global-CP is unable to find a feasible solution within one hour for scenarios 3 to 5, but, for the smaller scenarios, the solution quality is better and does improve over time. Thus, the PDDL solver behaves by prioritizing feasibility while mostly ignoring the objective function and the CP solver more aggressively optimizes the objective function, but can do so at the cost of not being able to find a schedule.

Decomposed-CP performs the best as it is able to consistently find solutions of high quality. The decomposition is able to find schedules with the maximum number of possible participants for every scenario and in general does so very quickly. Once a partial schedule is found with decisions made regarding the presence of a Bingo game and its players, the problem becomes significantly easier as many actions with cascading dependencies are eliminated. There is a large reduction in the number of charging tasks (about 98%) and reminder tasks (between 80% and 96%).

5 Conclusion

The properties of the retirement home environment create a complex problem to solve. Based on numerical experiments, we find that CP, in particular a decomposition model using CP, is the most suitable technology to use in our system.

CP is better equipped than PDDL planning for handling optimization, but can struggle to find feasible schedules for larger problems. We found that CP is better at obtaining high quality solutions, but it is interesting to note that the best approach is to only consider a simple objective function. Although the large number of optional tasks used in the CP model is also a culprit for the poor performance, we suspect for similar problems with complex objective functions, it is easier and likely just as effective to decompose a CP model to handle the objective function in stages rather than to remove or reduce the optional activities. We conclude that CP is better suited for our application; however, we do not claim that CP will be better than PDDL-based planning for all robot applications. To state one obvious case, CP is an inappropriate choice if the bound on the number of tasks to perform is either very poor or undefined.

Our full paper [Tran et al., 2017] presents more details of our work including: the full models, along with five alternative PDDL models; the modeling limitations and feature support of available solvers; a number of problem modifications that are also studied to obtain insights on the problem characteristics that are difficult for the solving technologies; and, lastly, a discussion of each of the technologies, the effects of modeling decisions, and a comparison between planning and scheduling.

Acknowledgements

The authors would like to thank the Natural Sciences and Engineering Research Council of Canada, Dr. Robot Inc., and the Technology Evaluation in the Elderly Network (which is supported by the Government of Canada through the Networks of Centres of Excellence).