Computing time optimal motions along specified paths forms an integral part of the solution methodology for many motion planning problems. Conventionally, this optimal control problem is solved considering piece-wise constant parametrization for the control input which leads to convexity and sparsity in the optimization structure. However, it also results in discontinuous control trajectory which is difficult to track. Thus, in this paper we revisit this time optimal control problem with the primary motivation of ensuring a high degree of smoothness in the resulting motion profile. In particular, we solve it with continuity constraints in control and higher order motion derivatives like jerk, snap etc. It is clear that such constraints would necessitate the use of time varying control inputs over the commonly used piece-wise constant form. The primary contribution of the current work lies in the introduction of a C ∞ class of time scaling functions represented as parametric exponentials. This in turn allows us to represent time varying control inputs as products of parametric exponential and a polynomial functions. We present the motivation behind adopting such representation of time scaling function over more common polynomial forms, both from mathematical as well as implementation standpoint. We also show that the proposed representation of time scaling function and control input leads to a very simple optimization structure where most of the constraints are linear. The non-linearity has a quasi-convex structure which can be reformulated into a simple difference of convex form. Thus, the resulting optimization can be efficiently solved through sequential convex programming where, at each iteration, the constraints in difference of convex form are further simplified to more conservative linear constraints.
Trajectory optimizations encountered in mobile robot navigation are non-convex, and thus the solution process is prone to get stuck at poor local optima, resulting in collisions with the environment. A conceptually simple workaround is to simply run the optimizer from several initializations in parallel and choose the best solution. But realizing this simple trick with off-the-shelf optimizers is challenging since they are not customized for parallel/batch operation. We fill this gap by proposing a novel batchable and GPU accelerated trajectory optimizer for autonomous navigation. Our batch optimizer can run several hundred instances of the problem in parallel in real time. We improve the state-of-the-art in the following respects. First, we show that parallel initialization naturally discovers a distribution of locally optimal trajectories residing in different homotopies. Second, we improve the navigation quality (success rate, tracking) compared to the baseline approach that relies on computing a single locally optimal trajectory at each control loop. Finally, we show that when initialized with trajectory samples from a Gaussian distribution, our batch optimizer out-performs the state-of-the-art cross-entropy method in solution quality. Codes: https://tinyurl.com/a3b99m8, Video: https://www.youtube.com/watch?v=ZlWJk-w03d8
Efficient navigation in unknown and dynamic environments is crucial for expanding the application domain of mobile robots. The core challenge stems from the nonavailability of a feasible global path for guiding optimization-based local planners. As a result, existing local planners often get trapped in poor local minima. In this paper, we present a novel optimizer that can explore multiple homotopies to plan high-quality trajectories over long horizons while still being fast enough for real-time applications. We build on the gradient-free paradigm by augmenting the trajectory sampling strategy with a projection optimization that guides the samples toward a feasible region. As a result, our approach can recover from the frequently encountered pathological cases wherein all the sampled trajectories lie in the high-cost region. Furthermore, we also show that our projection optimization has a highly parallelizable structure that can be easily accelerated over GPUs. We push the state-of-the-art in the following respects. Over the navigation stack of the Robot Operating System (ROS), we show an improvement of 7-13% in success rate and up to two times in total travel time metric. On the same benchmarks and metrics, our approach achieves up to 44% improvement over MPPI and its recent variants. On simple point-to-point navigation tasks, our optimizer is up to two times more reliable than SOTA gradient-based solvers, as well as sampling-based approaches such as the Cross-Entropy Method (CEM) and VPSTO. Codes: https://github.com/fatemeh-rastgar/PRIEST
An evolutionary algorithm (EA) is known as a subset of evolutionary computation. It is inspired by natural evolution and applies natural phenomena to search for the optimal solution. Its parallel search capability and randomized nature enable it to be effective and unique in solving different real-world problems in comparison to existing classical optimization algorithms. The evolutionary algorithm applies biological techniques such as selection, reproduction, and mutation to solve complex problems. It starts with a random population of candidate solutions and applies biological techniques to every generation until feasible solutions are obtained. The only fit solutionis intelligence (AI) simulation human intelligence in machines. Machines are programmed enough to think like humans and imitate their actions. AI based models are developed to provide new solutions to real-world problems. As realworld problems are very complex, the desired solutions for such problems are required to be explored in complex, high-dimensional, and very large search spaces. In this context, nature inspired and population based evolutionary techniques are the most suitable approach to find the optimal solution. The nature-inspired evolutionary techniques follow the natural phenomenon and these phenomenon helps to search for the desired optimal solution when the direction of the search is allowed to survive and continue to move in further generations to determine the optimal solution. Artificial not known at the beginning. So, “Evolutionary Artificial Intelligence (EAI)” is the term that presents the combination of human intelligence and natural phenomenon-based solutions to real-world complex problems. This chapter covers an overview of optimization techniques, artificial intelligence, and evolutionary computation in detail. A detailed discussion on evolutionary artificial intelligence, followed by applications of evolutionary machine learning is also presented. After that, the significance of evolutionary artificial intelligence in decision making has been discussed. Finally, the conclusion has been given, which shows the summary of the chapter.
In this paper we consider the problem of coordinating the motion of the manipulator and the vehicle to produce stable trajectories for the combined mobile manipulator system on uneven terrain. These kinds of situations often arise in planetary exploration, where rovers equipped with a manipulator are required to navigate over general uneven terrain. Moreover the framework can also be used in situations where the mobile manipulator is required to transport objects on uneven terrain. We generate feasible trajectories for the vehicle between a given start and a goal point considering the dynamics of the manipulator. The framework proposed in the paper plans such motion profile of the manipulator that maximizes vehicle stability which is measured by a novel concept called Feasible Acceleration Count (FAC). We show that, from the point of view of motion planning of mobile manipulator on uneven terrains, FAC gives a better estimate of vehicle stability than more popular metrics like Tip-Over Stability. The trajectory planner closely resembles motion primitive based graph based planning and is combined with a novel cost function derived from FAC. The efficacy of the approach is shown through simulations of a mobile manipulator system on a 2.5D uneven terrain.
In this paper, we propose a novel trajectory optimization algorithm for mobile manipulators under end-effector path, collision avoidance and various kinematic constraints. Our key contribution lies in showing how this highly non-linear and non-convex problem can be solved as a sequence of convex unconstrained quadratic programs (QPs). This is achieved by reformulating the non-linear constraints that arise out of manipulator kinematics and its coupling with the mobile base in a multi-affine form. We then use techniques from Alternating Direction Method of Multipliers (ADMM) to formulate and solve the trajectory optimization problem. The proposed ADMM has two similar non-convex steps. Importantly, a convex surrogate can be derived for each of them. We show how large parts of our optimization can be solved in parallel providing the possibility of exploiting multi-core CPUs/GPUs. We validate our trajectory optimization on different benchmark examples. Specifically, we highlight how it solves the cyclicity bottleneck and provides a holistic approach where diverse set of trajectories can be obtained by trading-off different aspects of manipulator and mobile base motion.
Navigation amongst densely packed crowds remains a challenge for mobile robots. The complexity increases further if the environment layout changes, making the prior computed global plan infeasible. In this paper, we show that it is possible to dramatically enhance crowd navigation by just improving the local planner. Our approach combines generative modelling with inference time optimization to generate sophisticated long-horizon local plans at interactive rates. More specifically, we train a Vector Quantized Variational AutoEncoder to learn a prior over the expert trajectory distribution conditioned on the perception input. At run-time, this is used as an initialization for a sampling-based optimizer for further refinement. Our approach does not require any sophisticated prediction of dynamic obstacles and yet provides state-of-the-art performance. In particular, we compare against the recent DRL-VO approach and show a 40% improvement in success rate and a 6% improvement in travel time.
In this paper we introduce a novel framework of generating trajectories which explicitly satisfies the stability constraints such as no-slip and permanent ground contact on uneven terrain. The main contributions of this paper are: (1) It derives analytical functions depicting the evolution of the vehicle on uneven terrain. These functional descriptions enable us to have a fast evaluation of possible vehicle stability along various directions on the terrain and this information is used to control the shape of the trajectory. (2) It introduces a novel paradigm wherein non-linear time scaling brought about by parametrized exponential functions are used to modify the velocity and acceleration profile of the vehicle so that these satisfy the no-slip and contact constraints. We show that nonlinear time scaling manipulates velocity and acceleration profile in a versatile manner and consequently has exceptional utility not only in uneven terrain navigation but also in general in any problem where it is required to change the velocity of the robot while keeping the path unchanged like collision avoidance.
Exploration is a core and important robotics area, whose applications include search and rescue robotics, planetary exploration etc. We know that this exploration task is best performed when using a multi-robot system. In this paper, we present an algorithm for multi-robot exploration of an unknown environment, taking into account the communication constraints between the robots. The aim of the robots is to explore the whole map as a pack, without losing communication throughout. The key task for us here is to allocate the target points for multiple robots so as to maximize the area explored and minimize the time and plan paths for the robots in such a way so as to avoid obstacles. A multi-robot exploration methodology is introduced similar to depth first strategy, that samples frontier points based on a metric function. This function aims to maximize the visibility gain or information gain while minimizing the distance to be travelled to the frontier points, such that the robots are within the limited communication distance of each other. The algorithm has been tested through simulation runs of various maps and results and evaluations have been presented based on it. The results effectively demonstrate that our algorithm allows robot pack to quickly accomplish the task of exploration and without the constraint ever breaking down. Here, we also present a comparative analysis of our algorithm with another exploration approach, which finds new areas based on population generation and utility calculation over the population. The results show tangible performance gain of this method over previous methods reported on exploration with limited communication constraints.
'%3e%3ccircle r='20' fill='%23008'/%3e%3ccircle r='17.5' fill='%23fff'/%3e%3ccircle r='3.5' fill='%23008'/%3e%3cg id='d'%3e%3cg id='c'%3e%3cg id='b'%3e%3cg id='a' fill='%23008'%3e%3ccircle r='.875' transform='rotate(7.5 -8.75 133.5)'/%3e%3cpath d='M0 17.5.6 7 0 2l-.6 5L0 17.5z'/%3e%3c/g%3e%3cuse xlink:href='%23a' transform='rotate(15)'/%3e%3c/g%3e%3cuse xlink:href='%23b' transform='rotate(30)'/%3e%3c/g%3e%3cuse xlink:href='%23c' transform='rotate(60)'/%3e%3c/g%3e%3cuse xlink:href='%23d' transform='rotate(120)'/%3e%3cuse xlink:href='%23d' transform='rotate(-120)'/%3e%3c/g%3e%3c/svg%3e)
