Sanjeev Sharma

This paper presents an efficient algorithm for online avoidance of static obstacles that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated incrementally by avoiding obstacles optimally one at a time, thus reducing the original problem from one that avoids m obstacles to m simpler problems that avoid one obstacle each. The computational complexity of this planner is therefore linear in the number of obstacles, instead of the typical… Show more

This paper presents an efficient algorithm for online avoidance of static obstacles that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated incrementally by avoiding obstacles optimally one at a time, thus reducing the original problem from one that avoids m obstacles to m simpler problems that avoid one obstacle each. The computational complexity of this planner is therefore linear in the number of obstacles, instead of the typical exponential complexity of traditional geometric planners. This approach is quite general and applicable to any cost function and to any robot dynamics; it is treated here for minimum time motions, a planar point mass robot, and circular obstacles. Numerical experiments demonstrate the algorithm for very cluttered environments (70 obstacles) and narrow passages. Upper and lower bounds on the motion time and on the path length were derived as functions of the Euclidean distance between the end points and the average obstacle size. Comparing a kinematic version of this algorithm to the RRT and RRT* planners showed significant advantages over both the planners. The algorithm was demonstrated on an experimental mobile robot moving at high speeds in a known environment. Show less

In this paper, we study the problem of learning the structure of Markov Networks which permit efficient inference. We formulate our problem as an optimization problem to maximize the likelihood of the model such that the inference complexity on the resulting structure is bounded. The inference complexity is measured with respect to any chosen algorithm (either exact or approximate), or a distribution over any marginal or conditional query. We relate our work to previous approaches for learning… Show more

In this paper, we study the problem of learning the structure of Markov Networks which permit efficient inference. We formulate our problem as an optimization problem to maximize the likelihood of the model such that the inference complexity on the resulting structure is bounded. The inference complexity is measured with respect to any chosen algorithm (either exact or approximate), or a distribution over any marginal or conditional query. We relate our work to previous approaches for learning bounded tree-width models and arithmetic circuits. The main contribution of our work is to isolate the inference penalty from the incremental structure building process. We show that our algorithm can be used to learn networks which bound the inference time of both exact and approximate algorithms. Further, we show that bounding inference time for approximate inference
results in networks that exhibit less approximation error. Show less

On-line motion planning in unknown environments is a challenging problem as it requires (i) ensuring collision avoidance and (ii) minimizing the motion time, while continuously predicting where to go next. Previous approaches to on-line motion planning assume that a rough map of the environment is available, thereby simplifying the problem. This paper presents a reactive on-line motion planner, Robust Autonomous Waypoint generation (RAW), for mobile robots navigating in unknown and unstructured… Show more

On-line motion planning in unknown environments is a challenging problem as it requires (i) ensuring collision avoidance and (ii) minimizing the motion time, while continuously predicting where to go next. Previous approaches to on-line motion planning assume that a rough map of the environment is available, thereby simplifying the problem. This paper presents a reactive on-line motion planner, Robust Autonomous Waypoint generation (RAW), for mobile robots navigating in unknown and unstructured environments. RAW generates a locally maximal ellipsoid around the robot, using semi-definite programming, such that the surrounding obstacles lie outside the ellipsoid. A reinforcement learning agent then generates a local waypoint in the robot’s field of view, inside the ellipsoid. The robot navigates to the waypoint and the process iterates until it reaches the goal. By following the waypoints the robot navigates through a sequence of overlapping ellipsoids, and avoids collision. Robot’s safety is guaranteed theoretically and the claims are validated through rigorous numerical experiments in four different experimental setups. Near-optimality is shown empirically by comparing RAW trajectories with the global optimal trajectories. Show less

This paper introduces a reinforcement learning (RL) based autonomous waypoint generation strategy (AWGS), for on-line path planning in unknown environments. An RL agent intelligently analyzes its surroundings and generates waypoints within the robot’s field of view. The RL agent uses an MDP for waypoint generation that is formulated to be independent of the domain, robot model, and state space dimensionality. The RL agent requires no environment-specific information beyond the robot’s field of… Show more

This paper introduces a reinforcement learning (RL) based autonomous waypoint generation strategy (AWGS), for on-line path planning in unknown environments. An RL agent intelligently analyzes its surroundings and generates waypoints within the robot’s field of view. The RL agent uses an MDP for waypoint generation that is formulated to be independent of the domain, robot model, and state space dimensionality. The RL agent requires no environment-specific information beyond the robot’s field of view. A path to the selected waypoint is then generated by a path planner. AWGS is applicable to many path or motion planners. However, for brevity, this paper focuses on path planning without the robot’s dynamics constraint. Experiments (i) compare the performance of RL agent’s policies with RRTs and A⋆, and (ii) show that AWGS can: (a) be trained and then used with different robot models, domains, and state-spaces, and (b) successfully navigate in environments with non-convex obstacles. Show less

This paper presents an efficient algorithm for on-line obstacle avoidance that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated on-line by avoiding obstacles, optimally, one at a time. The trajectory is generated recursively using a basic algorithm that plans trajectory segments to intermediate goals. The use of intermediate goals ensures safety and convergence to the global goal. This approach reduces the original problem of avoiding m… Show more

This paper presents an efficient algorithm for on-line obstacle avoidance that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated on-line by avoiding obstacles, optimally, one at a time. The trajectory is generated recursively using a basic algorithm that plans trajectory segments to intermediate goals. The use of intermediate goals ensures safety and convergence to the global goal. This approach reduces the original problem of avoiding m obstacles to m simpler problems of avoiding one obstacle each, producing a planner that is linear, instead of exponential, in the number of obstacles. Show less

This paper presents an efficient algorithm for online obstacle avoidance that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated on-line by avoiding obstacles optimally one at a time. This reduces the original problem from one with m obstacles to m simpler problems with one obstacle each, thus resulting in a
planner that is linear, instead of exponential, in the number of
obstacles. While this approach is quite general and… Show more

This paper presents an efficient algorithm for online obstacle avoidance that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated on-line by avoiding obstacles optimally one at a time. This reduces the original problem from one with m obstacles to m simpler problems with one obstacle each, thus resulting in a
planner that is linear, instead of exponential, in the number of
obstacles. While this approach is quite general and applicable
to any cost function and to any robot dynamics, it is treated
here for minimum time motions, a point mass robot, and planar
circular obstacles. Show less

Abstract: This paper presents a convex-QCQP based novel path planning algorithm named ellipsoidal constrained agent navigation (ECAN), for a challenging problem of online path planning in completely unknown and unseen continuous environments. ECAN plans path for the agent by making a tunnel of overlapping ellipsoids, in an online fashion, through the environment. Convex constraints in the ellipsoid-formation step circumvent collision with the obstacles. The problem of online-tunneling is solved… Show more

Abstract: This paper presents a convex-QCQP based novel path planning algorithm named ellipsoidal constrained agent navigation (ECAN), for a challenging problem of online path planning in completely unknown and unseen continuous environments. ECAN plans path for the agent by making a tunnel of overlapping ellipsoids, in an online fashion, through the environment. Convex constraints in the ellipsoid-formation step circumvent collision with the obstacles. The problem of online-tunneling is solved as a convex-QCQP. This paper assumes no constraints on shape of the agent and the obstacles. However, to make the approach clearer, this paper first introduces the framework for a point-mass agent with point-size obstacles. After explaining the underlying principle in drawing an ellipsoid tunnel, the framework is extended to the agent and obstacles having finite area (2d space) and finite-volume (3d-space). Show less

This paper introduces a novel waypoints selection framework for autonomous navigation in unknown and continuous environments, which may use a number of existing path planners. The Autonomous Waypoint Selection Framework (AWSF) is domain- and space-independent framework, which selects waypoints within an agent’s field-of-view. Each waypoint is treated as a temporary goal location, allowing the agent to eventually reach the goal state. Using AWSF, both local and global path planning algorithms… Show more

This paper introduces a novel waypoints selection framework for autonomous navigation in unknown and continuous environments, which may use a number of existing path planners. The Autonomous Waypoint Selection Framework (AWSF) is domain- and space-independent framework, which selects waypoints within an agent’s field-of-view. Each waypoint is treated as a temporary goal location, allowing the agent to eventually reach the goal state. Using AWSF, both local and global path planning algorithms can be used for online local waypoint planning. The key benefits of AWSF are: (i) allowing the agent to navigate in unknown and unseen spaces, using waypoints, with any path planning algorithm; (ii) significantly reducing planning time of existing planners by reducing the workspace; and (iii) learning in 2D spaces but automatically generalizing to planning in 3D-spaces. We empirically evaluate our framework with 5 path planning algorithms: an A* planner, an unconstrained cubic spline interpolation in both 2D- and 3Dspaces, the 2D- and 3D-ECAN planners, and a MILP-based dynamically feasible trajectory planner. Show less