提出了一种新的多Agent系统分散轨迹生成算法。多机器人系统具有改变各种领域生活的能力。但是,多机器人系统的轨迹生成仍处于初期阶段,仅限于严格控制的环境。为此,提出了一种在给定初始状态和期望结果姿势时为机器人生成无碰撞轨迹的在线轨迹优化算法。它利用一种简单的障碍物检测方法,基于局部形状的障碍物地图和机器人当前状态的通信。使用当地地图,制定安全区域。基于通信数据,预测其他机器人的轨迹,并通过调整机器人可以在没有碰撞的自由空间区域的大小来结合以避免碰撞。然后优化轨迹,使机器人保持在安全区域内,其中轨迹由按时间参数化的分段多项式表示。该算法使用后退时域原理实现。所提出的算法是在结构化和结构化环境中使用具有四阶差分平面空中机器人和非完整二阶轮式机器人的ROS对Gazebo的广泛测试的模拟。
translated by 谷歌翻译
在本文中,我们提出了一种时间有效的方法,为障碍物 - 环境中的四旋翼飞行器生成安全,平滑的动态可行轨迹。通过使用均匀B样条来表示轨迹,将轨迹规划湿转换为离散空间中B样条控制点的图搜索问题。 B样条的高度严格的凸壳性质来源于保证整个轨迹的动态可行性。采用Anovel非均匀动力学搜索策略,根据Euclideansigned distance field(ESDF)在搜索过程中动态调整步长,使轨迹达到合理的时间分配,远离障碍物。允许使用非静态初始状态和目标状态,因此它可用于在线本地重新计划以及全局规划。大量的仿真和硬件实验表明,与最先进的方法相比,我们的方法获得了更高的性能。
translated by 谷歌翻译
自主航拍摄影技术有可能在不需要人工干预的情况下自动捕获美观的视频,使个人具备高端电影制片厂的能力。当前的方法要么只处理离线轨迹生成,要么提供短期时间推理的策略和障碍的简单表示,这会导致运动不稳定和实际应用性低。在这项工作中,我们开发了一种能够交易的空中拍摄方法即使在嘈杂的演员预测下,原则上的合成平滑度,遮挡和电影摄影指南也是如此。我们提出了一种新的实时协变梯度下降算法,我们通过优化一组成本函数来有效地找到所需的轨迹。实验结果表明,我们的方法创造了有吸引力的镜头,在1.25小时的飞行时间内避开了障碍物和阻塞65次,在5秒时重新规划了10秒的时间范围。我们使用各种镜头类型,有力地拍摄人类演员,汽车和自行车,在障碍物之间进行不同的运动。
translated by 谷歌翻译
There is extensive literature on using convex optimization to derive piece-wise polynomial trajectories for controlling differential flat systems with applications to 3-D flight for Micro Aerial Vehicles (MAVs). In this work, we propose a method to formulate trajectory generation as a Quadratic Program (QP) using the concept of a Safe Flight Corridor (SFC). The SFC is a collection of convex overlapping polyhedra that models free space and provides a connected path from the robot to the goal position. We derive an efficient convex decomposition method that builds the SFC from a piece-wise linear skeleton obtained using a fast graph search technique. The SFC provides a set of linear inequality constraints in the QP allowing real-time motion planning. Because the range and field of view of the robot's sensors are limited, we develop a framework of Receding Horizon Planning which plans trajectories within a finite footprint in the local map, continuously updating the trajectory through a re-planning process. The re-planning process takes between 50 to 300 milliseconds for a large and cluttered map. We show the feasibility of our approach, its completeness and performance, with applications to high-speed flight in both simulated and physical experiments using quadrotors.
translated by 谷歌翻译
We consider the problem of generating motion plans for a robot that are guaranteed to succeed despite uncertainty in the environment, parametric model uncertainty, and disturbances. Furthermore, we consider scenarios where these plans must be generated in real-time, because constraints such as obstacles in the environment may not be known until they are perceived (with a noisy sensor) at runtime. Our approach is to pre-compute a library of "funnels" along different maneuvers of the system that the state is guaranteed to remain within (despite bounded disturbances) when the feedback controller corresponding to the maneuver is executed. We leverage powerful computational machinery from convex optimization (sums-of-squares programming in particular) to compute these funnels. The resulting funnel library is then used to sequentially compose motion plans at runtime while ensuring the safety of the robot. A major advantage of the work presented here is that by explicitly taking into account the effect of uncertainty, the robot can evaluate motion plans based on how vulnerable they are to disturbances. We demonstrate and validate our method using extensive hardware experiments on a small fixed-wing airplane avoiding obstacles at high speed (∼12 mph), along with thorough simulation experiments of ground vehicle and quadrotor models navigating through cluttered environments. To our knowledge, these demonstrations constitute one of the first examples of provably safe and robust control for robotic systems with complex nonlinear dynamics that need to plan in real-time in environments with complex geometric constraints.
translated by 谷歌翻译
Motion planning is an extremely well-studied problem in the robotics community, yet existing work largely falls into one of two categories: computationally efficient but with few if any safety guarantees, or able to give stronger guarantees but at high computational cost. This work builds on a recent development called FaSTrack in which a slow offline computation provides a modular safety guarantee for a faster online planner. We introduce the notion of "meta-planning" in which a refined offline computation enables safe switching between different online planners. This provides autonomous systems with the ability to adapt motion plans to a priori unknown environments in real-time as sensor measurements detect new obstacles, and the flexibility to maneuver differently in the presence of obstacles than they would in free space, all while maintaining a strict safety guarantee. We demonstrate the meta-planning algorithm both in simulation and in hardware using a small Crazyflie 2.0 quadrotor.
translated by 谷歌翻译
This paper presents a new approach to guaranteeing collision avoidance with respect to moving obstacles that have constrained dynamics but move unpredictably. Velocity Obstacles have been used previously to plan trajecto-ries that avoid collisions with obstacles under the assumption that the trajectories of the objects are either known or can be accurately predicted ahead of time. However, for real systems this predicted trajectory will typically only be accurate over short time-horizons. To achieve safety over longer time periods, this paper instead considers the set of all reachable points by an obstacle assuming that the dynamics fit the unicycle model, which has known constant forward speed and a maximum turn rate (sometimes called the Du-bins car model). This paper extends the Velocity Obstacle formulation by using reachability sets in place of a single "known" trajectory to find matching constraints in velocity space, called Velocity Obstacle Sets. The Velocity Obstacle Set for each obstacle is equivalent to the union of all velocity obstacles corresponding to any dynamically feasible future trajectory, given the obstacle's current state. This region remains bounded as the time horizon is increased to infinity , and by choosing control inputs that lie outside of these Velocity Obstacle Sets, it is guaranteed that the host agent can always actively avoid collisions with the obstacles, even without knowing their exact future trajectories. Furthermore it is proven that, subject to certain initial conditions, an iterative planner under these constraints guarantees safety for all time. Such an iterative planner is implemented and demonstrated in simulation.
translated by 谷歌翻译
We present a practical approach to global motion planning and terrain assessment for ground robots in generic three-dimensional (3D) environments, including rough outdoor terrain, multilevel facilities, and more complex geometries. Our method computes optimized six-dimensional trajectories compliant with curvature and continuity constraints directly on unordered point cloud maps, omitting any kind of explicit surface reconstruction, discretization, or topology extraction. We assess terrain geometry and traversability on demand during motion planning, by fitting robot-sized planar patches to the map and analyzing the local distribution of map points. Our motion planning approach consists of sampling-based initial trajectory generation, followed by precise local optimization according to a custom cost measure, using a novel, constraint-aware trajectory optimization paradigm. We embed these methods in a complete autonomous navigation system based on localization and mapping by means of a 3D laser scanner and iterative closest point matching, suitable for both static and dynamic environments. The performance of the planning and terrain assessment algorithms is evaluated in offline experiments using recorded and simulated sensor data. Finally, we present the results of navigation experiments in three different environments-rough outdoor terrain, a two-level parking garage, and a dynamic environment, demonstrating how the proposed methods enable autonomous navigation in complex 3D terrain. C 2016 Wiley Periodicals, Inc.
translated by 谷歌翻译
这项工作解决了将无人驾驶飞行器(UAV)的基于视觉的导航系统与强大的避障能力相结合的问题。前者通过最大化兴趣点可见度来制定,而后者则通过椭圆形排斥区域来建模。整个问题被转化为最优控制问题(OCP),并通过利用最先进的数值优化在几毫秒内解决。由此产生的轨迹非常适合于实现指定的目标位置,同时通过安全边缘避开障碍物并最小化与目标目标松散轨迹的概率。将该技术与适当的椭球形状相结合(例如,用障碍物速度增大形状,或者障碍物检测不确定性)导致强大的避障行为。我们在广泛的模拟实验中验证了我们的方法,证明了(i)满足所有约束的能力,以及(ii)甚至在挑战中的回避反应性。我们在本文中发布了开源实现
translated by 谷歌翻译
We present a new optimization-based approach for robotic motion planning among obstacles. Like CHOMP (Covariant Hamiltonian Optimization for Motion Planning), our algorithm can be used to find collision-free trajectories from naïve, straight-line initializations that might be in collision. At the core of our approach are (a) a sequential convex optimization procedure, which penalizes collisions with a hinge loss and increases the penalty coefficients in an outer loop as necessary, and (b) an efficient formulation of the no-collisions constraint that directly considers continuous-time safety Our algorithm is implemented in a software package called TrajOpt. We report results from a series of experiments comparing TrajOpt with CHOMP and randomized planners from OMPL, with regard to planning time and path quality. We consider motion planning for 7 DOF robot arms, 18 DOF full-body robots, statically stable walking motion for the 34 DOF Atlas humanoid robot, and physical experiments with the 18 DOF PR2. We also apply TrajOpt to plan curvature-constrained steerable needle trajectories in the SE(3) configuration space and multiple non-intersecting curved channels within 3D-printed implants for intracavitary brachytherapy. Details, videos, and source code are freely available at: http://rll.berkeley.edu/trajopt/ijrr.
translated by 谷歌翻译
Pat and Tedrake, Russ. "Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot." Autonomous Robots 40, 3 (March 2016): 429-455 Abstract This paper describes a collection of optimization algorithms for achieving dynamic planning, control, and state estimation for a bipedal robot designed to operate reliably in complex environments. To make challenging locomotion tasks tractable, we describe several novel applications of convex, mixed-integer, and sparse nonlinear optimization to problems ranging from footstep placement to whole-body planning and control. We also present a state estimator formulation that, when combined with our walking controller, permits highly precise execution of extended walking plans over non-flat terrain. We describe our complete system integration and experiments carried out on Atlas, a full-size hydraulic humanoid robot built by Boston Dynamics, Inc.
translated by 谷歌翻译
多机器人系统具有在各种应用中使用的潜力。在大多数先前的工作中,轨迹生成多机器人系统在已知环境中实现。为了克服这一点,我们提出了一种在线轨迹优化算法,该算法利用机器人当前状态的通信来考虑其他机器人,同时使用基于局部对象的地图来识别障碍物。基于这些数据,我们预测机器人预期要经过的轨迹,并通过制定机器人无需与其他机器人和障碍物碰撞的自由空间区域来利用这些轨迹来避免碰撞。优化轨迹以使机器人保持在该区域内。所提出的方法在使用ROS的Gazebo模拟中进行测试。
translated by 谷歌翻译
真实世界的自动驾驶车辆通常在先验的非知识环境中运行。由于这些系统中的大多数都是安全关键的,因此确保它们在面对环境不确定性(例如看不见的障碍物)时安全运行非常重要。当前的安全分析工具使得自治系统能够在给出有关环境状态的完整信息的情况下对安全性进行审查。但是,这些工具无法很好地适应实时感测环境的情况,例如在导航任务期间。在这项工作中,我们提出了一种基于哈密尔顿 - 雅可比可达性的新型实时安全分析方法,该方法在环境不确定的情况下提供了强有力的安全保证。我们的安全方法与计划者无关,并为各种测绘传感器提供保证。我们展示了我们的方法模拟和硬件,以围绕最先进的基于视觉的,基于学习的规划器提供安全保障。
translated by 谷歌翻译
Creative Commons Attribution-Noncommercial-Share Alike 3.0 Detailed Terms http://creativecommons.org/licenses/by-nc-sa/3.0/ The MIT Faculty has made this article openly available. Please share how this access benefits you. Your story matters. For motion planning problems involving many or unbounded forms of uncertainty , it may not be possible to identify a path guaranteed to be feasible, requiring consideration of the trade-off between planner conservatism and the risk of infeasibility. This paper presents a novel real-time planning algorithm, chance constrained rapidly-exploring random trees (CC-RRT), which uses chance constraints to guarantee probabilistic feasibility for linear systems subject to process noise and/or uncertain, possibly dynamic obstacles. By using RRT, the algorithm enjoys the computational benefits of sampling-based algorithms, such as trajectory-wise constraint checking and incorporation of heuristics, while explicitly incorporating uncertainty within the formulation. Under the assumption of Gaussian noise, prob-abilistic feasibility at each time step can be established through simple simulation of the state conditional mean and the evaluation of linear constraints. Alternatively, a small amount of additional computation can be used to explicitly compute a less conservative probability bound at each time step. Simulation results show that this algorithm can be used for efficient identification and execution of probabilistically safe paths in real time.
translated by 谷歌翻译
We present a framework for online generation of robust motion plans for robotic systems with nonlinear dynamics subject to bounded disturbances, control constraints, and online state constraints such as obstacles. In an offline phase, one computes the structure of a feedback controller that can be efficiently implemented online to track any feasible nominal trajectory. The offline phase leverages contraction theory and convex optimization to characterize a fixed-size "tube" that the state is guaranteed to remain within while tracking a nominal trajectory (representing the center of the tube). In the online phase, when the robot is faced with obstacles, a motion planner uses such a tube as a robustness margin for collision checking, yielding nominal trajectories that can be safely executed, i.e., tracked without collisions under disturbances. In contrast to recent work on robust online planning using funnel libraries, our approach is not restricted to a fixed library of maneuvers computed offline and is thus particularly well-suited to applications such as UAV flight in densely cluttered environments where complex maneuvers may be required to reach a goal. We demonstrate our approach through simulations of a 6-state planar quadrotor navigating cluttered environments in the presence of a crosswind. We also discuss applications of our approach to Tube Model Predictive Control (TMPC) and compare the merits of our method with state-of-the-art nonlinear TMPC techniques.
translated by 谷歌翻译
用于涉及飞行或移动摄像机的户外场景的自主运动捕捉(mocap)系统依赖于i)机器人前端在他/她执行身体活动时实时跟踪和跟踪人类主体,以及ii)算法后端从保存的视频中估计全身人体姿势和形状。在本文中,我们为我们的航空mocapsystem提供了一个新颖的前端,它由多个微型飞行器(MAV)组成,只有单板相机和计算。在以前的工作中,我们提出了一种使用多个MAV对受试者进行协作检测和跟踪(CDT)的方法。但是,它并没有确保MAV的最佳视点配置能够最大限度地提高人们协同跟踪的3D位置估计中的不确定性。在本文中,我们介绍了CDT的主动方法。相比之下,仅协作地跟踪人的3D位置,MAV可以现在主动地计算最佳局部运动计划,从而产生最佳视点配置,其最小化跟踪估计中的不确定性。通过将主动跟踪的目标解耦为对应于MAV的角度配置的凸二次目标和非凸约束来解决这个问题。此人。我们使用CDT算法中的高斯观察模式假设来推导它。我们还展示了我们如何嵌入所有非凸面约束,包括动态和静态障碍的约束,作为MPC动力学中的外部控制输入。在几个具有挑战性的情况下,提供了多个真实的机器人实验和比较,涉及3个MAV(视频链接:https://youtu.be/1qWW2zWvRhA)。广泛的仿真结果证明了我们方法的可扩展性和稳健性。还提供了基于ROS的源代码。
translated by 谷歌翻译
High-end vehicles are already equipped with safety systems, such as assistive braking and automatic lane following, enhancing vehicle safety. Yet, these current solutions can only help in low-complexity driving situations. In this work, we introduce a Parallel Autonomy, or shared control, framework that computes safe trajectories for an automated vehicle, based on human inputs. We minimize the deviation from the human inputs while ensuring safety via a set of collision avoidance constraints. Our method achieves safe motion even in complex driving scenarios, such as those commonly encountered in an urban setting. We introduce a receding horizon planner formulated as Nonlinear Model Predictive Control (NMPC), which includes analytic descriptions of road boundaries and the configuration and future uncertainties of other road participants. The NMPC operates over both steering and acceleration simultaneously. We introduce a nonslip model suitable for handling complex environments with dynamic obstacles, and a nonlinear combined slip vehicle model including normal load transfer capable of handling static environments. We validate the proposed approach in two complex driving scenarios. First, in an urban environment that includes a left-turn across traffic and passing on a busy street. And second, under snow conditions on a race track with sharp turns and under complex dynamic constraints. We evaluate the performance of the method with various human driving styles. We consequently observe that the method successfully avoids collisions and generates motions with minimal intervention for Parallel Autonomy. We note that the method can also be applied to generate safe motion for fully autonomous vehicles.
translated by 谷歌翻译
Self-driving vehicles are a maturing technology with the potential to reshape mobility by enhancing the safety, accessibility, efficiency, and convenience of automotive transportation. Safety-critical tasks that must be executed by a self-driving vehicle include planning of motions through a dynamic environment shared with other vehicles and pedestrians, and their robust executions via feedback control. The objective of this paper is to survey the current state of the art on planning and control algorithms with particular regard to the urban setting. A selection of proposed techniques is reviewed along with a discussion of their effectiveness. The surveyed approaches differ in the vehicle mobility model used, in assumptions on the structure of the environment, and in computational requirements. The side-by-side comparison presented in this survey helps to gain insight into the strengths and limitations of the reviewed approaches and assists with system level design choices.
translated by 谷歌翻译
Creative Commons Attribution-Noncommercial-Share Alike Detailed Terms http://creativecommons.org/licenses/by-nc-sa/4.0/ The MIT Faculty has made this article openly available. Please share how this access benefits you. Your story matters. Abstract We explore the challenges of planning trajectories for quadrotors through cluttered indoor environments. We extend the existing work on polynomial trajec-tory generation by presenting a method of jointly optimizing polynomial path segments in an unconstrained quadratic program that is numerically stable for high-order polynomials and large numbers of segments, and is easily formulated for efficient sparse computation. We also present a technique for automatically selecting the amount of time allocated to each segment, and hence the quadrotor speeds along the path, as a function of a single parameter determining aggressiveness, subject to actuator constraints. The use of polynomial trajectories, coupled with the differentially flat representation of the quadrotor, eliminates the need for computationally intensive sampling and simulation in the high dimensional state space of the vehicle during motion planning. Our approach generates high-quality trajectories much faster than purely sampling-based optimal kinodynamic planning methods, but sacrifices the guarantee of asymptotic convergence to the global optimum that those methods provide. We demonstrate the performance of our algorithm by efficiently generating trajectories through challenging indoor spaces and successfully traversing them at speeds up to 8 m/s. A demonstration of our algorithm and flight performance is available at: http://groups.csail.mit.edu/rrg/quad_polynomial_ trajectory_planning.
translated by 谷歌翻译
In this paper, we present a real-time approach to local trajectory replanning for microaerial vehicles (MAVs). Current trajectory generation methods for multicopters achieve high success rates in cluttered environments, but assume that the environment is static and require prior knowledge of the map. In the presented study, we use the results of such planners and extend them with a local replanning algorithm that can handle unmodeled (possibly dynamic) obstacles while keeping the MAV close to the global trajectory. To ensure that the proposed approach is real-time capable, we maintain information about the environment around the MAV in an occupancy grid stored in a three-dimensional circular buffer, which moves together with a drone, and represent the trajectories by using uniform B-splines. This representation ensures that the trajectory is sufficiently smooth and simultaneously allows for efficient optimization.
translated by 谷歌翻译