Paper Info
Title
A Constraint Programming Approach To Multi-Robot Task Allocation And Scheduling In Retirement Homes
Abstract
We study the application of constraint programming (CP) to the planning and scheduling of multiple social robots interacting with residents in a retirement home. The robots autonomously organize and facilitate group and individual activities among residents. The application is a multi-robot task allocation and scheduling problem in which task plans must be determined that integrate with resident schedules. The problem involves reasoning about disjoint time windows, inter-schedule task dependencies, user and robot travel times, as well as robot energy levels. We propose mixed-integer programming (MIP) and CP approaches for this problem and investigate methods for improving our initial CP approach using symmetry breaking, variable ordering heuristics, and large neighbourhood search. We introduce a relaxed CP model for determining provable bounds on solution quality. Experiments indicate substantial superiority of the initial CP approach over MIP, and subsequent significant improvements in the CP approach through our manipulations. This work is one of the few, of which we are aware, that applies CP to multi-robot task allocation and scheduling problems. Our results demonstrate the promise of CP scheduling technology as a general optimization infrastructure for such problems.
Year
DOI
Venue
2016
10.1007/978-3-319-44953-1_34
PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2016
Field
DocType
Volume
Social robot,Mathematical optimization,Job shop scheduling,Disjoint sets,Computer science,Scheduling (computing),Constraint programming,Schedule,Heuristics,Robot
Conference
9892
ISSN
Citations 
PageRank 
0302-9743
6
0.62
References 
Authors
11
3
Name
Order
Citations
PageRank
Kyle E. C. Booth193.07
Goldie Nejat229328.76
J. Christopher Beck391184.53