喜歡這套資料就充值下載吧。。。資源目錄里展示的都可在線預覽哦。。。下載后都有，，請放心下載，，文件全都包含在內(nèi)，，【有疑問咨詢QQ:1064457796 或 1304139763】 ===========================================喜歡這套資料就充值下載吧。。。資源目錄里展示的都可在線預覽哦。。。下載后都有，，請放心下載，，文件全都包含在內(nèi)，，【有疑問咨詢QQ:1064457796 或 1304139763】 ===========================================

IEEE TRANSACTIONS ON ROBOTICS, VOL. 24, NO. 5, OCTOBER 2008 1199 Real-Time Adaptive Motion Planning (RAMP) of Mobile Manipulators in Dynamic Environments With Unforeseen Changes John Vannoy and Jing Xiao, Senior Member, IEEE AbstractThis paper introduces a novel and general real-time adaptive motion planning (RAMP) approach suitable for plan- ning trajectories of high-DOF or redundant robots, such as mobile manipulators, in dynamic environments with moving obstacles of unknown trajectories. The RAMP approach enables simultaneous path and trajectory planning and simultaneous planning and exe- cution of motion in real time. It facilitates real-time optimization of trajectories under various optimization criteria, such as min- imizing energy and time and maximizing manipulability. It also accommodates partially specified task goals of robots easily. The approach exploits redundancy in redundant robots (such as lo- comotion versus manipulation in a mobile manipulator) through loose coupling of robot configuration variables to best achieve ob- stacle avoidance and optimization objectives. The RAMP approach has been implemented and tested in simulation over a diverse set of task environments, including environments with multiple mobile manipulators. The results (and also the accompanying video) show that the RAMP planner, with its high efficiency and flexibility, not only handles a single mobile manipulator well in dynamic environ- ments with various obstacles of unknown motions in addition to static obstacles, but can also readily and effectively plan motions for each mobile manipulator in an environment shared by multiple mobile manipulators and other moving obstacles. IndexTermsAdaptive, dynamic obstacles of unknown motion, loose coupling, mobile manipulators, partially specified goal, real time, redundant robots, trajectory optimization. I. INTRODUCTION M OTION PLANNING is a fundamental problem in robotics1,2concernedwithdevisingadesirablemo- tion for a robot to reach a goal. Motion planning for high-DOF articulated manipulators or mobile manipulators is more chal- lenging than for mobile robots because the high-dimensional configuration space of a robot has little or no resemblance to the physical space that the robot works in, and how to construct Manuscript received May 16, 2007; revised December 13, 2007 and March 5, 2008. First published October 10, 2008; current version published October 31, 2008. This paper was recommended for publication by Associate Editor K. Yamane and Editor L. Parker upon evaluation of the reviewers comments. A preliminary part of this paper was presented at the IEEE International Con- ference on Intelligent Robots and Systems, Sendai, Japan, 2004. The authors are with the Intelligent, Multimedia and Interactive Systems (IMI) Laboratory, Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC 28223 USA (e-mail: jmvannoy ; xiaouncc.edu). This paper has supplementary downloadable material available at http:/ieeexplore.ieee.org, provided by the authors: a video showing the real- time planning and execution of mobile manipulator motion by our RAMP algorithm. This video is 14 MB in size. Color versions of one or more of the figures in this paper are available online at http:/ieeexplore.ieee.org. Digital Object Identifier 10.1109/TRO.2008.2003277 a configuration space higher than three dimensions efficiently remains a largely unsolved problem. A. Related Research on Motion Planning Randomized algorithms, such as the popular probabilistic roadmap (PRM) method 3 and rapidly exploring random tree (RRT) method 4, are found to be very effective in finding a collision-free path for a robot with high DOFs offline be- cause such algorithms avoid building the robots configuration space explicitly by sampling the configuration space. The PRM method has inspired considerable work on improving sampling and roadmap construction 2, including a recent paper 5 on producing compact roadmaps to better capture the different ho- motopic path groups. By building a tree rather than a graph, the RRTmethodismoresuitableforgeneratingapathinoneshotor generatingatrajectorydirectlyandthusmoresuitableforonline operation 6. Both methods have seen many variants 2. There are also methods for path planning based on ge- netic algorithms (GAs), or more broadly, evolutionary com- putation 7, 8, which are general frameworks of randomized search subject to user-defined optimization criteria. Such op- timization techniques have been used widely and successfully in many application domains 8, 9 to tackle NP-hard opti- mization problems. There are two major ways of applications. One straightforward way is to map a problem into the form suitable for a standard, off-the-shelf GA, solve it by running the GA, and then, map the results back to the application do- main. This one-size-fit-all approach is often not effective be- cause it forces artificial transformation of a problem into some- thing else that is confined in the format of a standard GA but may losecertain important nature of the original problem. Some GA-based path planning methods 10, 11 adopt such an ap- proach, where C-space is discretized into a grid, and a path is in terms of a fixed-length sequence of grid points. As the standard GA operates on fixed-length bit strings, search is often very slow. A more effective approach is to adopt the general idea of evolutionary computation to solve a problem in a more natural andsuitablerepresentation.Thepathplanningmethodsreported in 1214 belong to such a customized approach. A real-time pathplanningmethodisreportedin12for2DOFpointmobile robots, which is extended in 13 for 3 DOF point flying robots with specific constraints. A multiresolution path representation is proposed in 14 for path planning. However, all evolution- ary algorithms have a number of parameters that must be set appropriately, which is often not a trivial task. 1552-3098/$25.00 2008 IEEE 1200 IEEE TRANSACTIONS ON ROBOTICS, VOL. 24, NO. 5, OCTOBER 2008 Unlike path planning, motion planning has to produce an executable trajectory for a robot in configurationtime space, or CT-space, and not merely a geometrical path. A common approach is to conduct trajectory planning on the basis of a path generated by a path planner. A notable framework is the elastic strip method 15, which can deform a trajectory for a robot locallytoavoidmovingobstaclesinsideacollision-free“tunnel” that connects the initial and goal locations of the robot in a 3-D workspace. Such a “tunnel” is generated from a decomposition- based path planning strategy 16. The other approach is to conduct path and trajectory planning simultaneously. However, most effort in this category is focused on offline algorithms assumingthattheenvironmentiscompletelyknownbeforehand, i.e., static objects are known, and moving objects are known withknowntrajectories1720.Asfordealingwithunknown moving obstacles, only recently some methods were introduced for mobile robots 21, 22. The combination of mobility and manipulation capability makes a mobile manipulator applicable to a much wider range of tasks than a fixed-base manipulator or a mobile robot. For a mobile manipulator, a task goal state is often partially specified as either a configuration of the end-effector, which we call a place-to-place task, or a desired path (or trajectory) of the end- effector, which we call a contour-following task, and the target location/path of the base is often unspecified. Here, a major issue of motion planning is the coordination of the mobile base and the manipulator. This issue, as it involves redundancy resolution, presents both challenges and opportu- nities. There exists a rich literature addressing this issue from many aspects. Some researchers treat the manipulator and the mobile base together as a redundant robot in planning its path for place-to-place tasks 2325. Some focused on planning a sequence of “commutation configurations” for the mobile base when the robot was to perform a sequence of tasks 26, 27 subject to various constraints and optimization criteria. Others focused on coordinating the control of the mobile base and the manipulator in a contour-following task 28, 29 by trying to position the mobile base to maximize manipulability. Many considered nonholonomic constraints. While most of the existing work assumes known environ- ments with known obstacles for a mobile manipulator, a few researchers considered local collision avoidance of unknown, moving obstacles online. One method 30 used RRT as a local planner to update a roadmap originally generated by PRM to deal with moving obstacles. For contour-following tasks, an ef- ficient method 31 allows the base to adjust its path to avoid a moving obstacle if possible while keeping the end-effector fol- lowing a contour, such as a straight line. Another method 29 allowed the base to pause in order to let an unexpected obsta- cle pass while the arm continued its contour-following motion under an event-based control scheme. Other methods include one based on potential field 32 to avoid unknown obstacles and one based on a neuro-fuzzy controller 33 to modify the base motion locally to avoid a moving obstacle stably. There is also an online planner for the special purpose of planning the motions of two robot arms getting parts from a conveyer belt 34. However, we are not aware of any existing work that can plan motions of high-DOF robots globally among many unknown dynamic obstacles. B. Our Problem and Approach Planning high-DOF robot motion in such an environment of many unknown dynamic obstacles poses special challenges. First, planning has to be done in real time, cannot be done of- fline, and cannot be based on a certain prebuilt map because the environment is constantly changing in unforeseen ways, i.e., the configuration space obstacles are unknown and changing. Examples of such environments include a large public square full of people moving in different ways, a warehouse full of busy-moving robots and human workers, and so on. Such an environment is very different from static or largely static envi- ronments or known dynamic environments (i.e., with other ob- ject trajectories known), where motion planning can reasonably rely on exploring C-space (for known static environments) or CT-space(forknowndynamicenvironments)offline(suchasby PRM). The elastic strip method provides the flexibility to make small adjustments of a robot motion to avoid unknown motions of obstacles, if the underlying topology of the C-space does not change. For an environment with changing C-space topology in unknown ways, a planned path/trajectory can be invalidated completelyatanytime,andthus,real-timeadaptiveglobalplan- ning capability is required for making drastic changes of robot motion. Planning and execution of motion should be simulta- neous and based on sensing so that planning has to be very fast and always able to adapt to changes of the environment. By nature, to tackle motion planning in an unknown dynamic environment cannot result in a complete planning algorithm. That is, no algorithm can guarantee success in such an unknown environment. We can only strive for a rational algorithm that serves as the “best driver of a high-DOF robot, but even the best driver cannot guarantee to be accident-free if other things in the environment are not under his/her control. This paper addresses the problem of real-time simultaneous path and trajectory planning of high-DOF robots, such as mobile manipulators, performing general place-to-place tasks in a dynamic environment with obstacle motions unknown. The obstacle motions can obstruct either the base or the arm or both of a mobile manipulator. We introduce a unique and general real-time adaptive motion planning (RAMP) approach. Our RAMP approach is built upon both the idea of randomized planning and that of the anytime, parallel, and optimized planning of evolutionary computation, while avoiding the drawbacks. The result is a unique and original approach effective for the concerned problem. The RAMP approach has the following characteristics. 1) Whole trajectories are represented at once in CT-space and constantly improved during simultaneous plan- ning and execution, unlike algorithms that build a path/trajectory sequentially (or incrementally) so that a wholepath/trajectorycanbecomeavailableonlyattheend of the planning process. Our anytime planner can provide a valid trajectory quickly and continue to produce better VANNOY AND XIAO: REAL-TIME ADAPTIVE MOTION PLANNING (RAMP) OF MOBILE MANIPULATORS IN DYNAMIC ENVIRONMENTS 1201 trajectories at any later time to suit the need of real-time global planning. 2) Different optimization criteria (such as minimizing en- ergy and time and optimizing manipulability) can be accommodated flexibly and easily in a seamless fash- ion. Optimization is done directly in the original, con- tinuous CT-space rather than being confined to a certain limited graph or roadmap. Trajectories are planned and optimized directly rather than conditional to the results of path planning. 3) Our planner is intrinsically parallel with multiple diverse trajectories present all the time to allow instant, and if necessary, drastic adjustment of robot motion to adapt to newly sensed changes in the environment. This is differ- ent from planners capable of only local trajectory adjust- ment based on a known set of homotopic paths. It is also different from sequential planners, such as anytime A* search 35, which also requires building a discrete state space for searcha limitation that our planner does not have. 4) Trajectory search and evaluation (of its optimality) are constantly adaptive to changes but built upon the results of previous search (i.e., knowledge accumulated) to be efficient for real-time processing. 5) As planning and execution (i.e., robot motion following the planned result so far) are simultaneous, partially feasi- ble trajectories are allowed, and the robot may follow the feasible part of such a trajectory (if it is the current best) and switch to a better trajectory to avoid the infeasible part. 6) With multiple trajectories from our planner, each trajec- tory can end at a different goal location in a goal region, i.e., partially specified goals, rather than a single goal con- figuration. 7) Our planner represents a trajectory for a redundant robot, such as a mobile manipulator, as loosely coupled trajec- tories of redundant variables to take advantage of the re- dundancy in order to best achieve obstacle avoidance and various optimization objectives. The rest of the paper is organized as follows. Section II pro- vides an overview of our RAMP approach; Sections III and IV describe problem representation and initialization; Section V outlines our optimization criteria for trajectory evaluation and describes the strategies for evaluation. Sections VI and VII de- scribe the strategies to alter trajectories to produce better ones. Section VIII describes how the RAMP planner can create and preserve a diverse set of trajectories. Section IX provides im- plementation and experimentation results and discusses perfor- mance of the planner. Section X concludes the paper. II. OVERVIEW OF THE RAMP APPROACH Onebasicpremiseofourapproachisthattheplanningprocess and the execution of motion are interweaving to enable simul- taneous robot motion planning and execution. This is achieved through our anytime planning algorithm that always maintains a set of complete trajectories in the CT-space of the robot called a population. The feasibility and optimality of each trajectory, called fitness, is evaluated through an evaluation function cod- ing the optimization criteria. Feasibility refers to collision-free andsingularity-free.Bothinfeasibleandfeasibletrajectoriesare allowed in a population. Feasible trajectories are considered fit- ter than infeasible trajectories. Within each type, trajectories are compared for optimality in fitness. Theinitialpopulationisacombinationofrandomlygenerated and deliberately seeded trajectories. Deliberately seeded trajec- tories include ones constructed to represent distinct subpopula- tionsinordertoachievecertaindiversityinthepopulation.Ifthe environment contains known static obstacles, trajectories based on preplanned feasible paths with respect to the known static obstacles can also be included. See Section IV for more details. Once the initial population is formed, it is then improved to a fitterpopulationthroughiterationsofimprovements,calledgen- erations. In each generation, a trajectory is randomly selected andalteredbyarandomlyselectedmodificationoperatoramong a number of different modification operators, and the resulting trajectory may be used to replace a trajectory that is not the fittest to form a new generation. The fittest trajectory is always kept in the population and can only improve from generation to generation. Each generation is also called a planning cycle. To improve the fitness of the initial population, a number of initial planning cycles may be run based on the initial sensing information of the environment before the robot begins execut- ing the fittest trajectory. The robot need not wait for a feasible trajectory to emerge; if no feasible trajectory is available, the robot will begin moving along the fittest in feasible trajectory while continuing the search for a fitter, and hopefully will locate a feasible trajectory before it comes within a distance threshold D of the first predicted collision or singularity of the executed trajectory. This strategy makes sense because: 1) the presently predicted infeasible trajectory may become feasible later and vice versa; 2) as to be described later, our planner makes the robot switch to a better trajectory if one is available, and thus, before the infeasible part of the currently followed trajectory is encountered, the robot may already switch to a better trajectory; 3) the strategy allows limited sensing, in which the robot may not sense an obstacle until getting closer; and 4) it provides a measure of safety in trajectory evaluation (see Section V). As the robot moves, planning continues to improve the popu- lation of trajectories until the next control cycle, when the robot can switch to a fitter trajectory so that it always follows the best trajectory. For that purpose, each trajectory is always updated to start from the current robot configuration with the current velocity when a new control cycle begins. For the trajectory that is being followed, this means that the executed portion of the trajectory is dropped from the trajectory, while for every other trajectory, it means that only the starting configuration and ve- locity are changedthe rest of the knot points on the trajectory (see Section III) remain intact. Note that each control cycle here does not necessarily have to be a servo cycle of the low-level controller. Our control cycle, which is high level for controlling the rate of adaptation, can be longer than a servo cycle to ensure that within a control cycle, there can be more than one planning cycle. This is because adaptation is guided by planning. 1202 IEEE TRANSACTIONS ON ROBOTICS, VOL. 24, NO. 5, OCTOBER 2008 Fig. 1. Relationship among planning, control, and sensing cycles. Changes in a dynamic environment are sensed and fed to the planner in each sensing cycle, which lead to updated fitness values of trajectories in the subsequent planning cycles, and unknown motions of moving obstacles are predicted in fitness evaluation of robot trajectories. The presence of a diverse popu- lationofever-improvingtrajectoriesenablestherobottoquickly adapt to changes in the environment. It does so by following the fittest trajectory under each circumstance: when the current tra- jectory that the robot follows becomes worse or can no longer be followed due to imminent collision (i.e., the threshol