ILOG Academic License Grant /
Powering Smarter Software
Please complete form, save and email as attachment to: .
1) Project Name: Multirobot Coordination for Urban Search and Rescue
2) Please describe your project or projects, keeping the description to at most one page single space. Where there is the potential for the development of new areas of application for underlying ILOG technologies, these should be mentioned, including the development of specific, new educational programs that focus on these technologies. A list of any other grants received or applied for in related areas should also be included, as well as a list of all participants in the present project and their affiliations. Target completion dates should be given for the proposed project(s).
Project Participants:
Mary KoesGraduate StudentThe Robotics Institute, CarnegieMellonUniversity
Illah NourbakhshAssociate ProfessorThe Robotics Institute, CarnegieMellonUniversity
Katia SycaraResearch ProfessorThe Robotics Institute, CarnegieMellonUniversity
6th Century Chair in Computing ScienceUniversity of Aberdeen, UK
Related Grants:
National Science Foundation Award IIS-0205526 (This grant did not provide for software purchases and recently expired)
Project Description: Target completion date: Summer 2007
The dangerous and time sensitive nature of a disaster area makes it an ideal application for robotic exploration. Our long term goal is to enable teams of humans, software agents, and autonomous robots to work together to save lives. Our research focuses on coordinating a team of heterogeneous robots to accomplish a set of goals in the disaster environment. Robot teams in these domains will necessarily be heterogeneous as cost limitations, power consumption, and size constraints require tradeoffs between mobility and capabilities. The tasks are tightly coupled in that robots must frequently work together on joint goals, either when no single robot possesses all the necessary capabilities or to improve team performance. Since the probability of successfully rescuing victims decreases over time, the goals must be accomplished as quickly as possibly.
Our research addresses the problem where a heterogeneous robot team is given some initial map of the environment marked with a set of goals to be accomplished. There may be additional constraints on the goals, robots, or resources of the system. The robot team must generate a plan at a level of abstraction suitable for execution by a robot with a typical three tiered architecture. This requires robots to solve the path planning, scheduling, and task allocation problems. While existing work in multirobot coordination decomposes the problem and addresses each subproblem separately, we use an MILP model as a basis for our unified framework, COCoA (Constraint Optimization Coordination Architecture).
Due to the uncertainty inherent in a disaster environment, the plans generated by the robots must often be refined. Robots can fail or discover inconsistencies in the map; goals can be added or discovered to take longer than anticipated; additional constraints can be added to the ordering of the goals or the resources in the system, to give a few examples. The unique nature of each disaster environment makes it difficult to model this uncertainty ahead of time. Instead robots must interleave planning and execution. Since the problem is NP-hard, even the best MILP solvers are unable to guarantee solutions in the time available for replanning online. We have developed an anytime algorithm that combines CPLEX’s strength in solving MILPs with common heuristics in multirobot coordination.
Another interesting component to the problem is that reliable communication is unavailable in a disaster area. Robots communicating with wireless Ethernet are only able to communicate when within some range dictated by the geometry of the environment. We model this with fractured subteams which are groups of robots that can communicate, directly or indirectly, with no communication between fractured subteams. This introduces a new dynamic variable into the system which must be considered during replanning. Since other subteams are unaware of disturbances within the system, care must be taken to minimize disruption to the schedules of these robots, particularly in the near term. The MILP framework allows us to incorporate this knowledge in a principled way by optimizing over multiple objective functions.
This current line of research is inspired by our work in developing search and rescue robot teams which we have demonstrated in the RoboCup Rescue competition, developed by NIST. We have built an abstract simulator, COCoAsim, to test the various heuristics and algorithms. We are, however, in the process of porting our work over to USARsim, a high fidelity search and rescue simulator, developed in cooperation with NIST and based on the Unreal game engine. We plan to demonstrate our work in the RoboCup Rescue Virtual Robots competition at RoboCup 2006 in Bremen this July.
With our experience in both the fields of multirobot coordination and developing physical robots for urban search and rescue, we are in a unique position to help the robotics community appreciate the power of optimization techniques and, in particular, ILOG products. Multirobot coordination differs from traditional applications for OR in that the planners are spatially distributed and yet each capable of planning. This presents a wide range of possibilities for improving performance by decomposing the problem and allowing multiple robots to participate in the optimization, an area that we are interested in exploring in the future.
3) We are always interested in learning more about how people are using ILOG technology. Upon completion of your project(s), please send us copies of any published or submitted papers or application demos that benefited from your granted ILOG license(s). If there are other, potentially relevant materials you could send, please note these in our proposal.
Publications which have benefited from ILOG technology to date:
M. Koes, I. Nourbakhsh, and K. Sycara. "Constraint Optimization Coordination Architecture for Search and Rescue Robotics", in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), May 2006 (accepted). (
M. Koes, K. Sycara, and I. Nourbakhsh. "A Constraint Optimization Framework for Fractured Robot Teams", in Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2006 (accepted). (
M. Koes, K. Sycara, and I. Nourbakhsh. "The Best Laid Plans of Robots and Men", in Proceedings of the AAAI Spring Symposium on Distributed Plan and Schedule Management, Stanford University, AAAI Press, March 2006. (
M. Koes, I. Nourbakhsh, and K. Sycara. "Heterogeneous Multirobot Coordination with Spatial and Temporal Constraints," in Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI), AAAI Press, June, 2005, pp. 1292-1297. (
Also currently available: Ph.D. thesis proposal, “A Constraint Based Approach to Interleaving Planning and Execution for Multirobot Coordination” by Mary Koes, Carnegie Mellon University Robotics Institute, Dec. 15, 2005. (
The proposed thesis and relevant demos rely on ILOG CPLEX and will also be available when completed.
Please note that the publications listed above acknowledge ILOG’s previous assistance to our project (in the form of an additional discount). We will continue to acknowledge ILOG’s support in our future work.
Primary Grant Contact: Mary Koes
(Submits the proposal & signs the agreement)
Title: Graduate Student
Department: The Robotics Institute, CarnegieMellonUniversity
Phone: 412-268-7019
Fax: 412-268-5569
Email:
Administrator: Mary Koes
(Installs and maintains software)
Title: Graduate Student
Department: The Robotics Institute, CarnegieMellonUniversity
Phone: 412-268-7019
Email:
Product License(s) Being Requested:
(Academic License Grants are offered for one-year terms.)
CPLEX development license
Thank you for your interest in ILOG technology and for completing this form.
Please email as attachment to: .
Your request will be reviewed within the next week.
If your grant request is approved, you will receive an approval letter and a Grant License Agreement that must be signed and returned (via fax to 775-881-2801) before your grant license can be fulfilled.
To be completed by ILOG
ILOG Sponsor (if applicable):
Grant Request Reviewed By (Product Specific Committee):
Approved:
Not Approved:
Reason:
Commercial Value of Grant:
Grant Renewal Date:
ILOG Deliverable Follow Up Date:
Request for ILOG Academic License Grant – Jan02ILOG Direct / Page 1 of 3