Carnegie Mellon University Robotics Institute Homepage

Carnegie Mellon University Robotics Institute Research Guide

Carnegie Mellon University, Robotics Institute, Research Guide

Planning & Scheduling

RI has had a strong research presence in the core area of planning and scheduling since its establishment. Planning and scheduling research at the RI covers a broad scope, from motion control and action planning for individual robots, to efficient coordination of robot teams, to optimizing behavior in large-scale automated or semi-automated systems. Current projects reflect this diversity, ranging from maneuver planning for autonomous vehicles to coordinated, multi-robot path planning for search and rescue to adaptive traffic signal control for urban road networks.

Several RI researchers focus on basic aspects of robot planning – the various prediction problems that autonomous robotic systems must solve to complete tasks. These problems include motion planning for mobile manipulation and articulated robots (Likhachev), motion planning for legged and bipedal robots (Atkeson, Veloso), and path planning for unmanned air and ground vehicles (Likhachev, Singh). One common challenge is achieving efficient and safe behaviors in the face of uncertainty, both in the effects of initiated actions and in the external operating environment. Approximate dynamic programming using trajectory libraries is being explored as one means of achieving (near) optimal motion control (Atkeson). This approach is similar to reinforcement learning. Other researchers (Likhachev, Stentz) are developing graph representations and heuristic graph search algorithms for motion and path planning that can search high dimensional graphs in real-time and deal well with uncertainty. Variable level of detail planning is being investigated for planning collision-free trajectories in dynamic environments with poorly predictable moving objects (Veloso). Some recent significant applications of developed motion and path planning techniques include maneuver planning in the winning DARPA Urban Challenge vehicle in 2007 (Likhachev) and autonomous flight planning in the Boeing Unmanned Little Bird helicopter (Singh).

Another broad thrust of planning and scheduling research at RI aims at coordinating teams of robots (and more generally teams of agents) in the execution of tasks. Current work spans such problems as planning for tight coordination of heterogeneous robots engaged in complex tasks (e.g., construction of large beam and node structures) that cannot be completed by a singe robot (Simmons, Singh), multi-robot path planning for coverage, surveillance, search and large-team applications (Singh, Scerri, Sycara), collaborative task planning and scheduling of heterogeneous teams in dynamic environments involving continual new task discovery (Dias, Rubinstein, Smith), robot soccer (Veloso), and execution-driven task scheduling and resource allocation in large-scale, multi-actor systems (Smith). In these general settings also, the basic challenge is robust optimization in the presence of execution dynamics and uncertainty. Solution approaches include both centralized and distributed search procedures for efficient probabilistic reasoning (Simmons, Singh, Smith), market-based mechanisms for task and resource allocation (Dias, Stentz), constraint-based search and optimization (Smith), distributed prioritized planning (Scerri, Sycara) and playbook-based team coordination (Veloso).

Several researchers (Dias, Simmons, Smith, Sycara, Veloso) emphasize frameworks for mixed-initiative task planning and scheduling, and for human steering of robot and multi-robot systems. Another emerging research focus aims at bridging the gap between task and motion planning in robot and multi-robot systems (Likhachev, Smith, Veloso). Machine learning techniques are being used increasingly to acquire planning models (Bagnell).

The current RI planning and scheduling faculty is comprised of a mix or senior and junior people that is further augmented through collaboration with faculty in other units of the School of Computer Science that work in related or complementary research areas. Relevant faculty in CSD, Machine Learning, HCII and LTI, as well as OR and OM faculty in the Tepper School of Business routinely co-advise or sit on the thesis committees of graduate students in planning and scheduling, and collaborate with RI planning and scheduling faculty on joint projects.

Continue Reading: Quality of Life Technology


Faculty

  1. Christopher
    Atkeson

  2. Drew
    Bagnell

  3. Bernardine
    Dias

  4. Maxim
    Likhachev

  5. Zach
    Rubinstein

  6. Paul
    Scerri

  7. Reid
    Simmons

  8. Sanjiv
    Singh

  9. Stephen
    Smith

  10. Tony
    Stentz

  11. Katia
    Sycara

  12. Manuela
    Veloso


Project Images

  • Trajectory-Based Optimal Control

  • TraderBots: Market-Based Task Allocation

  • Real-Time Motion Planning

  • Coordinated Multi-Robot Search for Emergency Response

  • Execution-Driven Planning and Schedulng

  • Distributed Coordination of Mobile Teams

  • Distributed Coordination of Mobile Teams

  • Learning, Planning and Locomotion

  • Inverse Optimal Control on Mobile Robots

  • Decentralized Prioritized Planning

  • Decentralized Prioritized Planning

  • Variable Level of Detail Planning

  • Adaptive, Real-Time Traffic Signal Control Strategies

  • Adaptive, Real-Time Traffic Signal Control Strategies