TL;DR
This paper tackles the complex challenge of coordinating a team of assistive robots in retirement homes to schedule daily activities for elderly residents. They propose and evaluate three approaches, finding that a decomposed Constraint Programming (CP) model significantly outperforms PDDL planning and a global CP model in terms of solution quality and efficiency.
What Problem Does This Paper Address?
The global population is aging, leading to increased demand for elder care. Retirement homes face a shortage of human caregivers, creating a need for assistive technologies. This paper focuses on a specific aspect of this challenge: how to effectively plan and schedule the daily activities of a team of socially assistive robots (like the Tangy robot) to engage elderly residents in recreational activities and provide necessary interactions. The core problem is to generate a daily plan that ensures all required single-user activities are scheduled, maximizes participation in optional multi-user activities (Bingo games), provides timely reminders, and does so efficiently while managing robot battery life and user availability. This is a complex multi-objective optimization problem with cascading dependencies, making it difficult for traditional planning and scheduling techniques.
Methods
The authors explore three distinct approaches:
- PDDL-Based Planning: This method uses Planning Domain Definition Language (PDDL) to model the problem. PDDL is a standard language for AI planning, where actions are defined with preconditions and effects. The planner then searches for a sequence of actions to achieve a goal state. This approach is good at finding feasible solutions but struggles with optimization.
- Global-CP: This approach uses Constraint Programming (CP), a powerful technique for solving combinatorial optimization problems. In Global-CP, all tasks (telepresence sessions, Bingo games, reminders, charging) are modeled as optional interval variables. The solver then tries to find an assignment of tasks to robots and users that satisfies all constraints and optimizes a multi-objective function. This method is better at optimization but can struggle to find feasible solutions within a reasonable time for complex problems.
- CP-Based Decomposition (Decomposed-CP): This is the novel contribution. Recognizing the limitations of Global-CP, they decompose the problem into two stages:
- Master Problem: A simplified Global-CP model with a primary objective of maximizing Bingo game participation. This stage quickly assigns users to games.
- Sub-problem: A more detailed CP model that takes the assignments from the master problem and optimizes the full objective function (including reminders, battery usage, etc.). This decomposition aims to handle cascading effects more effectively and improve solution quality and speed.
Datasets
The paper uses five "scenarios" to evaluate their models. These scenarios represent different configurations of the retirement home environment, varying the number of users, robots, telepresence sessions, and Bingo games. The user schedules and environment parameters were obtained from collaborating retirement homes. No new benchmark datasets were introduced; rather, existing real-world requirements were used to create test cases.
Key Insights and Ideas
- CP's Strength in Optimization: Constraint Programming is significantly better than PDDL planning at handling the multi-objective optimization aspect of this problem, leading to higher quality schedules.
- Decomposition is Key for Complexity: The cascading dependencies in this problem (e.g., a Bingo game requires a reminder, which requires user availability) make a single, large CP model computationally expensive. Decomposing the problem into stages (first assigning users to games, then optimizing the full schedule) dramatically improves performance.
- Reduced Task Overhead: The Decomposed-CP approach leads to a substantial reduction in the number of charging tasks (around 98%) and reminder tasks (80-96%) compared to the initial problem formulation, indicating a more efficient use of robot resources.
- Feasibility vs. Optimality Trade-off: PDDL planning prioritizes finding any feasible solution, often at the expense of quality (e.g., no Bingo games). Global-CP prioritizes quality but can fail to find feasible solutions for larger instances. Decomposed-CP strikes a better balance.
Key Results
The empirical evaluation (Table 2) shows:
- PDDL Planning: Always finds feasible solutions but with very low objective values, often not including any Bingo games. Runtimes are generally faster for smaller scenarios but increase significantly with complexity.
- Global-CP: Achieves better objective values than PDDL for smaller scenarios but fails to find feasible solutions within the one-hour time limit for scenarios 3, 4, and 5.
- Decomposed-CP: Consistently finds high-quality solutions across all scenarios, maximizing participants in Bingo games and achieving significantly better objective values than PDDL. It also finds solutions much faster than Global-CP for complex scenarios. For example, in scenario 5, Decomposed-CP achieves an objective value of 1,929.00, while PDDL achieves 27,554.54 (a higher value indicating worse performance).
Limitations and Future Work
- Limitations: The authors acknowledge that while Decomposed-CP performs best, it's not guaranteed to find the absolute optimal solution for the original problem due to the simplification in the master problem's objective. They also note that CP can struggle with problems where task bounds are very poor or undefined, making PDDL potentially more suitable in such cases.
- Future Work: The paper mentions that their full paper includes more details on modeling limitations, feature support of solvers, problem modifications, and a deeper comparison between planning and scheduling. The success of the decomposition suggests that exploring similar decomposition strategies for other complex planning and scheduling problems could be a fruitful avenue.
Summary updated