Real-time, Simulation-based Planning and Asynchronous Coordination for Cyber-Physical Systems
Abstract
Abstract for the National CPS PI Meeting 2012
Towards the development of robust cyber-physical systems, this project aims to develop frameworks and general solutions for motion planning and coordination for individual and networks of autonomous systems. This work is inspired by related challenges and techniques in algorithmic motion planning, multi-agent systems, sensor networks, learning and control. The focus of the project has been on the following tasks during the period 2011-2012:
• Methods for approximating cost-to-go metrics in the state-space of non-
holonomic and underactuated systems. An offline learning phase in obstacle- free environments is utilized and combined with multi-dimensional scaling for the efficient online utilization of the learned information. The technique requires access only to a forward propagation model of the system [Li, Bekris, ICRA 11].
•Methods for computing asymptotically near-optimal paths. Asymptotically optimal planners guarantee solutions approach optimal but roadmaps with this property can be slow to construct and grow too. Utilizing graph spanner tools, which provide near-optimal paths, asymptotically near-optimal planners have been developed. They result in large reductions in construction time, roadmap density and online-query resolution with a small sacrifice in path quality [Marble, Bekris ISRR 11-IROS 11-ICRA 12 / Dobson, Bekris WAFR 12 (invited to IJRR)].
•Safe motion coordination for multiple vehicles, which recompute their trajectories in an asynchronous manner. Planning must guarantee a robot’s safety by not bringing the robot to states where collisions cannot be avoided in the future. The safe operation of multiple communicating second-order vehicles, whose replanning cycles do not coincide, can be guaranteed through an asynchronous, distributed planning and communication framework [Grady, Bekris, Kavraki WAFR 10 – Bekris, Grady, Moll, Kavraki IJRR 12].
-
The project has also investigated reactive approaches for decentralized conflict resolution that are communication-less but aim towards guaranteeing the eventual resolution of a problem, i.e., providing liveness [Krontiris, Bekris IROS 11 / Kimmel, Bekris AAMAS 12].
-
Combinatorial methods for multi-agent path planning on discrete abstractions have been developed, which achieve sub-optimal solutions in polynomial time, while the problem is hard in the general case. This allows the efficient resolution of larger-scale path planning instances with competitive path lengths [Luna, Bekris IJCAI 11-IROS 11 / Sajid, Luna, Bekris SOCS 12].
Important outreach efforts were pursued including the development of open- source software [SIMPAR 2012]. The project involved undergraduate and graduate students, including women, in research activities related to CPS. The PI organized special meetings related to the project’s objectives gave lectures to the general public on CPS-related topics.
Award ID: 0932423 (transferred to 1252351)
Submitted by Kostas Bekris
on
Abstract
Abstract for the National CPS PI Meeting 2012
Towards the development of robust cyber-physical systems, this project aims to develop frameworks and general solutions for motion planning and coordination for individual and networks of autonomous systems. This work is inspired by related challenges and techniques in algorithmic motion planning, multi-agent systems, sensor networks, learning and control. The focus of the project has been on the following tasks during the period 2011-2012:
• Methods for approximating cost-to-go metrics in the state-space of non-
holonomic and underactuated systems. An offline learning phase in obstacle- free environments is utilized and combined with multi-dimensional scaling for the efficient online utilization of the learned information. The technique requires access only to a forward propagation model of the system [Li, Bekris, ICRA 11].
•Methods for computing asymptotically near-optimal paths. Asymptotically optimal planners guarantee solutions approach optimal but roadmaps with this property can be slow to construct and grow too. Utilizing graph spanner tools, which provide near-optimal paths, asymptotically near-optimal planners have been developed. They result in large reductions in construction time, roadmap density and online-query resolution with a small sacrifice in path quality [Marble, Bekris ISRR 11-IROS 11-ICRA 12 / Dobson, Bekris WAFR 12 (invited to IJRR)].
•Safe motion coordination for multiple vehicles, which recompute their trajectories in an asynchronous manner. Planning must guarantee a robot’s safety by not bringing the robot to states where collisions cannot be avoided in the future. The safe operation of multiple communicating second-order vehicles, whose replanning cycles do not coincide, can be guaranteed through an asynchronous, distributed planning and communication framework [Grady, Bekris, Kavraki WAFR 10 – Bekris, Grady, Moll, Kavraki IJRR 12].
-
The project has also investigated reactive approaches for decentralized conflict resolution that are communication-less but aim towards guaranteeing the eventual resolution of a problem, i.e., providing liveness [Krontiris, Bekris IROS 11 / Kimmel, Bekris AAMAS 12].
-
Combinatorial methods for multi-agent path planning on discrete abstractions have been developed, which achieve sub-optimal solutions in polynomial time, while the problem is hard in the general case. This allows the efficient resolution of larger-scale path planning instances with competitive path lengths [Luna, Bekris IJCAI 11-IROS 11 / Sajid, Luna, Bekris SOCS 12].
Important outreach efforts were pursued including the development of open- source software [SIMPAR 2012]. The project involved undergraduate and graduate students, including women, in research activities related to CPS. The PI organized special meetings related to the project’s objectives gave lectures to the general public on CPS-related topics.
Award ID: 0932423 (transferred to 1252351)