ECAN: The project was started with a vision that Convex Optimization and Reinforcement Learning can together result in a highly robust domain and space independent planner for autonomous navigation in completely unknown and unseen environments. This project then gave birth to DFRL-E project. See this video: ECAN

- ECAN: Path Planning in 2D and 3D-environments using Convex-Quadratic Constrained Quadratic Program (QCQP); Semi-Definite Programming (SDP); and Second Order Cone Programming (SOCP), (Published)

- R-ECAN: Reinforced-ECAN; Submitted in IROS-2012 (a sample run is shown in the left figure).

Aim: Developing a general path planner that can enable autonomous navigation in completely unknown and unseen environments (2D or 3D).

Properties and Robustness:
  1. Absolute zero prior knowledge of the environment or the obstacles they are discovered online.
  2. Due to convex formulation of the entire framework, solution is guaranteed at each time-step.
  3. No assumptions on shape of the agent: Agent can be convex or non-convex shaped - the algorithm uses Second Order Cone Programming to handle non-convex shaped agent (figure on the left)
  4. Uses point-cloud representation of obstacles discovered in the field-of-view during navigation: Exact boundary detection is not assumed
Convex-Reinforced Planning: Ellipsoidal Constrained Agent Navigation

Porject: Jan 2010 - Jul 2011
A path planning algorithm for planning online in completely unknown and unseen environments, with limited visibility, using convex optimization and reinforcement learning.
Outcomes: The ECAN project then resulted in the development of DFRL-E Project, which can generalize any existing path or motion planner.

Project Information:

The project Convex-Reinforced Planning (CRP) is divided into two parts: (i) ECAN and (ii) R-ECAN. The first part focussed on inventing a convex optimization based path planner named ECAN. The second part focuses on incorporating reinforcement learning as a guidance mechanism to devise a robust planner R-ECAN. The R-ECAN resulted into the DFRL-E or the AWSF framework, which has the capability of generalizing any existing path or motion planner, and performing beyond the capabilities of the planners.

ECAN: ECAN is a Convex-Quadratic Constrained Quadratic Programming (QCQP), Semi-Definite Programming (SDP) and Second-Order Cone Programming (SOCP) based path planner for planning in absolutely unknown and unseen continuous 2D- and 3D-environments. This planner uses only the information available in the robot &prime s field-of-view (FOV) to plan a path to the goal location. Robot has limited FOV. ECAN then forms a tunnel of overlapping ellipsoids (online) through the environment, to the goal location. ECAN doesn?t make any assumptions on shape of the agent or the obstacles. They can be convex or non-convex. ECAN uses a relaxed SOCP (or simply quadratic programming) to handle finite-size (finite area/volume) robot.

Published [1]

R-ECAN: A highly robust planning framework, which uses reinforcement learning to intelligently reason about where to navigate by locating a waypoint in the robot's FOV. This waypoint is then treated as the goal location by the ECAN planner, and it plans a path to reach there. By repeating this process, robust planning is done for navigation in completely unknown and unseen 2D- and 3D-environments. However, the framework described in the paper does not focus too much on ECAN. It mainly describes the DFRL-E framework with just one RL agent.

Accepted [2]

  1. Sanjeev Sharma, QCQP-Tunneling: Ellipsoidal Constrained Agent Navigation. In Proceedings of Second IASTED International Conference on Robotics (Robo), Nov 7-9, 2011, Pittsburgh, USA.
  2. Sanjeev Sharma and Matthew E. Taylor, Autonomous Waypoint Generation Strategy for On-Line Navigation in Unknown Environments. In Proceedings of IROS Workshop on Robot Motion Planning: Online Reactive and in Real-Time, 2012, Portugal.


  1. My first presentation for this project during February 2010: 
    Video Presentation - ECAN,  pdf - ECAN_CRP

  1. Path Planning channel of Searching:
    Here you will find two presentations, one on ECAN and one explaining the MINIMUM VOLUME ELLIPSOIDS.
    Path Planning Channel

  2. Link for all channels of searching-eye: Channels-SE

  3. See the work of George Konidaris on Skill Learning.