Real-Time, Simulation-based Planning and Asynchronous Coordination for Cyber-Physical Systems

Abstract:

Towards the development of robust cyber-physical systems, this project has developed solutions for planning and coordinating the motions of 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 2012-2013:

• Methods for computing asymptotically near-optimal paths in a computationally efficient manner. Asymptotically optimal planners guarantee solutions approach optimal but roadmaps with this property can be slow to construct and can quickly become large and dense. 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 ICRA 12 Marble, Bekris IEEE TRO 13/ Dobson, Bekris WAFR 12 and invited to appear at IJRR / Dobson ICRA 13]. Recently we have extended this kind of properties to the case of systems that have to respect different constraints in their motion or which employ a physics-based simulator in order to compute their motion [Littlefield, Bekris IROS 13].
• Identifying the finite-time properties of sampling-based methods for motion planning in terms of path quality. So far, all the guarantees were asymptotic in nature, which provided little insight regarding the practical use of these tools for real-world autonomous systems [Dobson, Bekris IROS 13].
• 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 [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 [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 computationally hard in the general case. This allows the efficient resolution of larger-scale path planning instances with competitive path lengths [Sajid, Luna, Bekris SOCS 12, Krontiris, Luna, Bekris SOCS 13].
• Important outreach efforts were pursued including the development of open-source software [SIMPAR 2012]. The project involved undergraduate and graduate students in research activities related to CPS, including under-represented groups in STEM. The PI organized special meetings related to the project's objectives gave lectures to the general public on CPS-related topics.