Enhancing Randomized Motion Planners Exploring with Haptic Hints

Optimal and Efficient Path Planning for Partially-Known EnvironmentsAnthony StentzThe Robotics Institute; Carnegie Mellon University; Pittsburgh, PA 15213AbstractThe task of planning trajectories for a mobile robot has received considerable attention in the research literature. Most of the work assumes the robot has a complete and accurate model of its environment before it begins to move; less attention has been paid to the problem of partially known environments. This situation occurs for an exploratory robot or one that must move to a goal location without the benefit of a floorplan or terrain map. Existing approaches plan an initial path based on known information and then modify the plan locally or replan the entire path as the robot discovers obstacles with its sensors, sacrificing optimality or computational efficiency respectively. This paper introduces a new algorithm, D*, capable of planning paths in unknown, partially known, and changing environments in an efficient, optimal, and complete manner.1.0IntroductionThe research literature has addressed extensively the motion planning problem for one or more robots moving through a field of obstacles to a goal. Most of this work assumes that the environment is completely known before the robot begins its traverse (see Latombe [4] for a good survey). The optimal algorithms in this literature search a state space (e.g., visibility graph, grid cells) using the dis-tance transform [2] or heuristics [8] to find the lowest cost path from the robot’s start state to the goal state. Cost can be defined to be distance travelled, energy expended, time exposed to danger, etc.Unfortunately, the robot may have partial or no information about the environment before it begins its traverse but is equipped with a sensor that is capable of measuring the environment as it moves. One approach to path planning in this scenario is to generate a “global”path using the known information and then attempt to “locally” circumvent obstacles on the route detected by the sensors [1]. If the route is completely obstructed, a new global path is planned. Lumelsky [7] initially assumes the environment to be devoid of obstacles and moves the robot directly toward the goal. If an obstacle obstructs the path, the robot moves around the perimeter until the point on the obstacle nearest the goal is found. The robot then proceeds to move directly toward the goal again. Pirzadeh [9] adopts a strategy whereby the robot wanders about the environment until it discovers the goal. The robot repeatedly moves to the adjacent location with lowest cost and increments the cost of a location each time it visits it to penalize later traverses of the same space. Korf [3] uses initial map information to estimate the cost to the goal for each state and efficiently updates it with backtracking costs as the robot moves through the environment.While these approaches are complete, they are also suboptimal in the sense that they do not generate the lowest cost path given the sensor information as it is acquired and assuming all known, a priori information is correct. It is possible to generate optimal behavior by computing an optimal path from the known map information, moving the robot along the path until either it reaches the goal or its sensors detect a discrepancy between the map and the environment, updating the map, and then replanning a new optimal path from the robot’s current location to the goal. Although this brute-force, replanning approach is optimal, it can be grossly inefficient, particularly in expansive environments where the goal is far away and little map information exists. Zelinsky [15] increases efficiency by using a quad-tree [13] to represent free and obstacle space, thus reducing the number of states to search in the planning space. For natural terrain, however, the map can encode robot traversability at each location ranging over a continuum, thus rendering quad-trees inappropriate or suboptimal.This paper presents a new algorithm for generating optimal paths for a robot operating with a sensor and a map of the environment. The map can be complete, empty, or contain partial information about the environment. ForIn Proceedings IEEE International Conference on Robotics and Automation, May 1994.regions of the environment that are unknown, the map may contain approximate information, stochastic models for occupancy, or even a heuristic estimates. The algorithm is functionally equivalent to the brute-force,optimal replanner, but it is far more efficient.The algorithm is formulated in terms of an optimal find-path problem within a directed graph, where the arcs are labelled with cost values that can range over a continuum. The robot’s sensor is able to measure arc costs in the vicinity of the robot, and the known and estimated arc values comprise the map. Thus, the algorithm can be used for any planning representation, including visibility graphs [5] and grid cell structures. The paper describes the algorithm, illustrates its operation, presents informal proofs of its soundness, optimality, and completeness, and then concludes with an empirical comparison of the algorithm to the optimal replanner.2.0The D* AlgorithmThe name of the algorithm, D*, was chosen because it resembles A* [8], except that it is dynamic in the sense that arc cost parameters can change during the problem-solving process. Provided that robot motion is properly coupled to the algorithm, D* generates optimal trajecto-ries. This section begins with the definitions and notation used in the algorithm, presents the D* algorithm, and closes with an illustration of its operation.2.1DefinitionsThe objective of a path planner is to move the robot from some location in the world to a goal location, such that it avoids all obstacles and minimizes a positive cost metric (e.g., length of the traverse). The problem space can be formulated as a set of states denoting robot loca-tions connected by directional arcs , each of which has an associated cost. The robot starts at a particular state and moves across arcs (incurring the cost of traversal) to other states until it reaches the goal state, denoted by . Every state except has a backpointer to a next state denoted by . D* uses backpointers to represent paths to the goal. The cost of traversing an arc from state to state is a positive number given by the arc cost function . If does not have an arc to , then is undefined. Two states and are neighbors in the space if or is defined.Like A*, D* maintains an list of states. The list is used to propagate information about changes to the arc cost function and to calculate path costs to states in the space. Every state has an associated tag ,such that if has never been on the list, if is currently on the list, andG X G Y b X ()Y =Y X c X Y ,()Y X c X Y ,()X Y c X Y ,()c Y X ,()OPEN OPEN X t X ()t X ()NEW =X OPEN t X ()OPEN =XOPEN if is no longer on the list. For each state , D* maintains an estimate of the sum of the arc costs from to given by the path cost function . Given the proper conditions, this estimate is equivalent to the optimal (minimal) cost from state to , given by the implicit function . For each state on the list (i.e.,), the key function,, is defined to be equal to the minimum of before modification and all values assumed by since was placed on the list. The key function classifies a state on the list into one of two types:a state if , and a state if . D* uses states on the listto propagate information about path cost increases (e.g.,due to an increased arc cost) and states to propagate information about path cost reductions (e.g.,due to a reduced arc cost or new path to the goal). The propagation takes place through the repeated removal of states from the list. Each time a state is removed from the list, it is expanded to pass cost changes to its neighbors. These neighbors are in turn placed on the list to continue the process.States on the list are sorted by their key function value. The parameter is defined to be for all such that . The parameter represents an important threshold in D*: path costs less than or equal to are optimal, and those greater than may not be optimal. The parameter is defined to be equal to prior to most recent removal of a state from the list. If no states have been removed,is undefined.An ordering of states denoted by is defined to be a sequence if for all such that and for all such that . Thus, a sequence defines a path of backpointers from to . A sequence is defined to be monotonic if( a n d) o r ( and ) for all such that . D* constructs and maintains a monotonic sequence , representing decreasing current or lower-bounded path costs, for each state that is or was on the list. Given a sequence of states , state is an ancestor of state if and a descendant of if .For all two-state functions involving the goal state, the following shorthand notation is used:.Likewise, for sequences the notation is used.The notation is used to refer to a function independent of its domain.t X ()CLOSED =X OPEN X X G h G X ,()X G o G X ,()X OPEN t X ()OPEN =k G X ,()h G X ,()h G X ,()X OPEN X OPEN RAISE k G X ,()h G X ,()<LOWER k G X ,()h G X ,()=RAISE OPEN LOWER OPEN OPEN OPEN k min min k X ()()X t X ()OPEN =k min k min k min k old k min OPEN k old X 1X N {,}b X i 1+()X i =i 1i ≤N <X i X j ≠i j (,)1i ≤j <N ≤X N X 1X 1X N {,}t X i ()CLOSED =h G X i ,()h G X i 1+,()<t X i ()OPEN =k G X i ,()h G X i 1+,()<i 1i ≤N <G X {,}X OPEN X 1X N {,}X i X j 1i j N ≤<≤X j 1j i N ≤<≤f X ()f G X ,()≡X {}G X {,}≡f °()2.2Algorithm DescriptionThe D* algorithm consists primarily of two functions: and .is used to compute optimal path costs to the goal, and is used to change the arc cost function and enter affected states on the list. Initially, is set to for all states,is set to zero, and is placed on the list. The first function,, is repeatedly called until the robot’s state,, is removed from the list (i.e.,) or a value of -1 is returned, at which point either the sequence has been computed or does not exist respectively. The robot then proceeds to follow the backpointers in the sequence until it eitherreaches the goal or discovers an error in the arc cost func-tion (e.g., due to a detected obstacle). The second function,, is immediately called to cor-rect and place affected states on the list. Let be the robot’s state at which it discovers an error in .By calling until it returns ,the cost changes are propagated to state such that . At this point, a possibly new sequence has been constructed, and the robot continues to follow the backpointers in the sequence toward the goal.T h e a l g o r i t h m s f o r a n d are presented below. The embedded routines are , which returns the state on the list with minimum value ( if the list is empty);, which returns for the list (-1 if the list is empty);, which deletes state from the list and sets ; and , w h i c h c o m p u t e s i f , if , and i f , s e t s and , and places or re-positions state on the list sorted by .In function at lines L1 through L3,the state with the lowest value is removed from the list. If is a state (i.e.,), its path cost is optimal since is equal to the old . At lines L8 through L13, each neighbor of is examined to see if its path cost can be lowered. Additionally,neighbor states that are receive an initial path cost value, and cost changes are propagated to each neighbor that has a backpointer to , regardless of whether the new cost is greater than or less than the old. Since these states are descendants of , any change to the path cost of affects their path costs as well. The backpointer of is redirected (if needed) so that the monotonic sequence is constructed. All neighbors that receive a new pathPROCESS STATE –MODIFY COST –PROCESS STATE –MODIFY COST –c °()OPEN t °()NEW h G ()G OPEN PROCESS STATE –X OPEN t X ()CLOSED =X {}X {}c °()MODIFY COST –c °()OPEN Y c °()PROCESS STATE –k min h Y ()≥Y h Y ()o Y ()=Y {}PROCESS STATE –MODIFY COST –MIN STATE –OPEN k °()NULL GET KMIN –k min OPEN DELETE X ()X OPEN t X ()CLOSED =INSERT X h new ,()k X ()h new =t X ()NEW =k X ()min k X ()h new ,()=t X ()OPEN =k X ()min h X ()h new ,()=t X ()CLOSED =h X ()h new =t X ()OPEN =X OPEN k °()PROCESS STATE –X k °()OPEN X LOWER k X ()h X ()=h X ()k min Y X NEW Y X X X Y Y {}cost are placed on the list, so that they will propagate the cost changes to their neighbors.If is a state, its path cost may not be optimal.Before propagates cost changes to its neighbors, its optimal neighbors are examined at lines L4 through L7 to see if can be reduced. At lines L15 through L18, cost changes are propagated to states and immediate descendants in the same way as for states. If is able to lower the path cost of a state that is not an immediate descendant (lines L20 and L21), is placed back on the list for future expansion. It is shown in the next section that this action is required to avoid creating a closed loop in the backpointers. If the path cost of is able to be reduced by a suboptimal neighbor (lines L23 through L25), the neighbor is placed back on the list. Thus, the update is “postponed” until the neighbor has an optimal path cost.Function: PROCESS-STATE ()L1L2if then return L3;L4if then L5for each neighbor of :L6if and then L7;L8if then L9for each neighbor of :L10if or L11( and ) or L12( and ) then L13;L14else L15for each neighbor of :L16if or L17( and ) then L18;L19else L20if and then L21L22else L23if and and L24 and then L25L26return OPEN X RAISE X h X ()NEW LOWER X X OPEN X OPEN X MIN STATE ()–=X NULL =1–k old GET KMIN –()=DELETE X ()k old h X ()<Y X h Y ()k old ≤h X ()h Y ()c Y X ,()+>b X ()Y =h X ()h Y ()c Y X ,()+=k old h X ()=Y X t Y ()NEW =b Y ()X =h Y ()h X ()c X Y ,()+≠b Y ()X ≠h Y ()h X ()c X Y ,()+>b Y ()X =INSERT Y h X ()c X Y ,()+,()Y X t Y ()NEW =b Y ()X =h Y ()h X ()c X Y ,()+≠b Y ()X =INSERT Y h X ()c X Y ,()+,()b Y ()X ≠h Y ()h X ()c X Y ,()+>INSERT X h X (),()b Y ()X ≠h X ()h Y ()c Y X ,()+>t Y ()CLOSED =h Y ()k old >INSERT Y h Y (),()GET KMIN ()–In function , the arc cost function is updated with the changed value. Since the path cost for state will change, is placed on the list. When is expanded via , it computes a new and places on the list.Additional state expansions propagate the cost to the descendants of .Function: MODIFY-COST (X, Y, cval)L1L2if then L3return 2.3Illustration of OperationThe role of and states is central to the operation of the algorithm. The states (i.e.,) propagate cost increases, and the states (i.e.,) propagate cost reductions. When the cost of traversing an arc is increased, an affected neighbor state is placed on the list, and the cost increase is propagated via states through all state sequences containing the arc. As the states come in contact with neighboring states of lower cost, these states are placed on the list, and they sub-sequently decrease the cost of previously raised states wherever possible. If the cost of traversing an arc isdecreased, the reduction is propagated via states through all state sequences containing the arc, as well as neighboring states whose cost can also be lowered.Figure 1: Backpointers Based on Initial PropagationFigure 1 through Figure 3 illustrate the operation of the algorithm for a “potential well” path planning problem.MODIFY COST –Y X OPEN X PROCESS STATE –h Y ()h X ()c X Y ,()+=Y OPEN Y c X Y ,()cval=t X ()CLOSED =INSERT X h X (),()GET KMIN ()–RAISE LOWER RAISE k X ()h X ()<LOWER k X ()h X ()=OPEN RAISE RAISE LOWER OPEN LOWER GThe planning space consists of a 50 x 50 grid of cells .Each cell represents a state and is connected to its eight neighbors via bidirectional arcs. The arc cost values are small for the cells and prohibitively large for the cells.1 The robot is point-sized and is equipped with a contact sensor. Figure 1 shows the results of an optimal path calculation from the goal to all states in the planning space. The two grey obstacles are stored in the map, but the black obstacle is not. The arrows depict the backpointer function; thus, an optimal path to the goal for any state can be obtained by tracing the arrows from the state to the goal. Note that the arrows deflect around the grey, known obstacles but pass through the black,unknown obstacle.Figure 2: LOWER States Sweep into WellThe robot starts at the center of the left wall and follows the backpointers toward the goal. When it reaches the unknown obstacle, it detects a discrepancy between the map and world, updates the map, colors the cell light grey, and enters the obstacle cell on the list.Backpointers are redirected to pull the robot up along the unknown obstacle and then back down. Figure 2illustrates the information propagation after the robot has discovered the well is sealed. The robot’s path is shown in black and the states on the list in grey.states move out of the well transmitting path cost increases. These states activate states around the1. The arc cost value of OBSTACLE must be chosen to be greater than the longest possible sequence of EMPTY cells so that a simple threshold can be used on the path cost to determine if the optimal path to the goal must pass through an obstacle.EMPTY OBSTACLE GLOWER statesRAISE statesLOWER statesOPEN OPEN RAISE LOWER“lip” of the well which sweep around the upper and lower obstacles and redirect the backpointers out of the well.Figure 3: Final Backpointer ConfigurationThis process is complete when the states reach the robot’s cell, at which point the robot moves around the lower obstacle to the goal (Figure 3). Note that after the traverse, the backpointers are only partially updated.Backpointers within the well point outward, but those in the left half of the planning space still point into the well.All states have a path to the goal, but optimal paths are computed to a limited number of states. This effect illustrates the efficiency of D*. The backpointer updates needed to guarantee an optimal path for the robot are limited to the vicinity of the obstacle.Figure 4 illustrates path planning in fractally generated terrain. The environment is 450 x 450 cells. Grey regions are fives times more difficult to traverse than white regions, and the black regions are untraversible. The black curve shows the robot’s path from the lower left corner to the upper right given a complete, a priori map of the environment. This path is referred to as omniscient optimal . Figure 5 shows path planning in the same terrain with an optimistic map (all white). The robot is equipped with a circular field of view with a 20-cell radius. The map is updated with sensor information as the robot moves and the discrepancies are entered on the list for processing by D*. Due to the lack of a priori map information, the robot drives below the large obstruction in the center and wanders into a deadend before backtracking around the last obstacle to the goal. The resultant path is roughly twice the cost of omniscientGLOWER OPEN optimal. This path is optimal, however, given the information the robot had when it acquired it.Figure 4: Path Planning with a Complete MapFigure 5: Path Planning with an Optimistic MapFigure 6 illustrates the same problem using coarse map information, created by averaging the arc costs in each square region. This map information is accurate enough to steer the robot to the correct side of the central obstruction, and the resultant path is only 6% greater incost than omniscient optimal.Figure 6: Path Planning with a Coarse-Resolution Map3.0Soundness, Optimality, andCompletenessAfter all states have been initialized to and has been entered onto the list, the function is repeatedly invoked to construct state sequences. The function is invoked to make changes to and to seed these changes on the list. D* exhibits the following properties:Property 1: If , then the sequence is constructed and is monotonic.Property 2: When the value returned by e q u a l s o r e x c e e d s , t h e n .Property 3: If a path from to exists, and the search space contains a finite number of states, will be c o n s t r u c t e d a f t e r a fi n i t e n u m b e r o f c a l l s t o . I f a p a t h d o e s n o t e x i s t , will return -1 with .Property 1 is a soundness property: once a state has been visited, a finite sequence of backpointers to the goal has been constructed. Property 2 is an optimality property.It defines the conditions under which the chain of backpointers to the goal is optimal. Property 3 is a completeness property: if a path from to exists, it will be constructed. If no path exists, it will be reported ina finite amount of time. All three properties holdX t X ()NEW =G OPEN PROCESS STATE –MODIFY COST –c °()OPEN t X ()NEW ≠X {}k min PROCESS STATE –h X ()h X ()o X ()=X G X {}PROCESS STATE –PROCESS STATE –t X ()NEW =X G regardless of the pattern of access for functions and .For brevity, the proofs for the above three properties are informal. See Stentz [14] for the detailed, formal p r o o f s. C o n s i d e r P r o p e r t y 1 fi r s t. W h e n e v e r visits a state, it assigns to point to an existing state sequence and sets to preserve monotonicity. Monotonic sequences are subsequently manipulated by modifying the functions ,,, and . When a state is placed on the list (i.e.,), is set to preserve monotonicity for states with backpointers to .Likewise, when a state is removed from the list, the values of its neighbors are increased if needed to preserve monotonicity. The backpointer of a state ,, can only be reassigned to if and if the sequence contains no states. Since contains no states, the value of every state in the sequence must be less than . Thus, cannot be an ancestor of , and a closed loop in the backpointers cannot be created.Therefore, once a state has been visited, the sequence has been constructed. Subsequent modifications ensure that a sequence still exists.Consider Property 2. Each time a state is inserted on or removed from the list, D* modifies values so that for each pair of states such that is and is . Thus, when is chosen for expansion (i.e.,), the neighbors of cannot reduce below , nor can the neighbors, since their values must be greater than . States placed on the list during the expansion of must have values greater than ; thus, increases or remains the same with each invocation of . If states with values less than or equal to are optimal, then states with values between (inclusively) and are optimal, since no states on the list can reduce their path costs. Thus, states with values less than or equal to are optimal. By induction,constructs optimal sequences to all reachable states. If the a r c c o s t i s m o d i fi e d , t h e f u n c t i o n places on the list, after which is less than or equal to . Since no state with can be affected by the modified arc cost, the property still holds.Consider Property 3. Each time a state is expanded via , it places its neighbors on the list. Thus, if the sequence exists, it will be constructed unless a state in the sequence,, is never selected for expansion. But once a state has been placedMODIFY COST –PROCESS STATE –PROCESS STATE –NEW b °()h °()t °()h °()k °()b °()X OPEN t X ()OPEN =k X ()h X ()X X h °()X b X ()Y h Y ()h X ()<Y {}RAISE Y {}RAISE h °()h Y ()X Y X X {}X {}OPEN h °()k X ()h Y ()c Y X ,()+≤X Y ,()X OPEN Y CLOSED X k min k X ()=CLOSED X h X ()k min OPEN h °()k min OPEN X k °()k X ()k min PROCESS STATE –h °()k old h °()k old k min OPEN h °()k min PROCESS STATE –c X Y ,()MODIFY COST –X OPEN k min h X ()Y h Y ()h X ()≤PROCESS STATE –NEW OPEN X {}Yon the list, its value cannot be increased.Thus, due to the monotonicity of , the state will eventually be selected for expansion.4.0Experimental ResultsD* was compared to the optimal replanner to verify its optimality and to determine its performance improve-ment. The optimal replanner initially plans a single path from the goal to the start state. The robot proceeds to fol-low the path until its sensor detects an error in the map.The robot updates the map, plans a new path from the goal to its current location, and repeats until the goal isreached. An optimistic heuristic function is used to focus the search, such that equals the “straight-line”cost of the path from to the robot’s location assuming all cells in the path are . The replanner repeatedly expands states on the list with the minimum value. Since is a lower bound on the actual cost from to the robot for all , the replanner is optimal [8].The two algorithms were compared on planning problems of varying size. Each environment was square,consisting of a start state in the center of the left wall and a goal state in center of the right wall. Each environment consisted of a mix of map obstacles (i.e., available to robot before traverse) and unknown obstacles measurable b y t h e r o b o t ’s s e n s o r. T h e s e n s o r u s e d w a s omnidirectional with a 10-cell radial field of view. Figure 7 shows an environment model with 100,000 states. The map obstacles are shown in grey and the unknown obstacles in black.Table 1 shows the results of the comparison for environments of size 1000 through 1,000,000 cells. The runtimes in CPU time for a Sun Microsystems SPARC-10processor are listed along with the speed-up factor of D*over the optimal replanner. For both algorithms, the reported runtime is the total CPU time for all replanning needed to move the robot from the start state to the goal state, after the initial path has been planned. For each environment size, the two algorithms were compared on five randomly-generated environments, and the runtimes were averaged. The speed-up factors for each environment size were computed by averaging the speed-up factors for the five trials.The runtime for each algorithm is highly dependent on the complexity of the environment, including the number,size, and placement of the obstacles, and the ratio of map to unknown obstacles. The results indicate that as the environment increases in size, the performance of D*over the optimal replanner increases rapidly. The intuitionOPEN k °()k min Y gˆX ()gˆX ()X EMPTY OPEN gˆX ()h X ()+g ˆX ()X X for this result is that D* replans locally when it detects an unknown obstacle, but the optimal replanner generates a new global trajectory. As the environment increases in size, the local trajectories remain constant in complexity,but the global trajectories increase in complexity.Figure 7: Typical Environment for Algorithm ComparisonTable 1: Comparison of D* to Optimal Replanner5.0Conclusions5.1SummaryThis paper presents D*, a provably optimal and effi-cient path planning algorithm for sensor-equipped robots.The algorithm can handle the full spectrum of a priori map information, ranging from complete and accurate map information to the absence of map information. D* is a very general algorithm and can be applied to problems in artificial intelligence other than robot motion planning. In its most general form, D* can handle any path cost opti-mization problem where the cost parameters change dur-ing the search for the solution. D* is most efficient when these changes are detected near the current starting point in the search space, which is the case with a robot equipped with an on-board sensor.Algorithm 1,00010,000100,0001,000,000Replanner 427 msec 14.45 sec 10.86 min 50.82 min D*261 msec 1.69 sec 10.93 sec 16.83 sec Speed-Up1.6710.1456.30229.30See Stentz [14] for an extensive description of related applications for D*, including planning with robot shape,field of view considerations, dead-reckoning error,changing environments, occupancy maps, potential fields,natural terrain, multiple goals, and multiple robots.5.2Future WorkFor unknown or partially-known terrains, recentresearch has addressed the exploration and map building problems [6][9][10][11][15] in addition to the path finding problem. Using a strategy of raising costs for previously visited states, D* can be extended to support exploration tasks.Quad trees have limited use in environments with cost values ranging over a continuum, unless the environment includes large regions with constant traversability costs.Future work will incorporate the quad tree representation for these environments as well as those with binary cost values (e.g., and ) in order to reduce memory requirements [15].Work is underway to integrate D* with an off-road obstacle avoidance system [12] on an outdoor mobile robot. To date, the combined system has demonstrated the ability to find the goal after driving several hundred meters in a cluttered environment with no initial map.AcknowledgmentsThis research was sponsored by ARPA, under contracts “Perception for Outdoor Navigation” (contract number DACA76-89-C-0014, monitored by the US Army TEC)and “Unmanned Ground Vehicle System” (contract num-ber DAAE07-90-C-R059, monitored by TACOM).The author thanks Alonzo Kelly and Paul Keller for graphics software and ideas for generating fractal terrain.References[1] Goto, Y ., Stentz, A., “Mobile Robot Navigation: The CMU System,” IEEE Expert, V ol. 2, No. 4, Winter, 1987.[2] Jarvis, R. A., “Collision-Free Trajectory Planning Using the Distance Transforms,” Mechanical Engineering Trans. of the Institution of Engineers, Australia, V ol. ME10, No. 3, Septem-ber, 1985.[3] Korf, R. E., “Real-Time Heuristic Search: First Results,”Proc. Sixth National Conference on Artificial Intelligence, July,1987.[4] Latombe, J.-C., “Robot Motion Planning”, Kluwer Aca-demic Publishers, 1991.[5] Lozano-Perez, T., “Spatial Planning: A Configuration Space Approach”, IEEE Transactions on Computers, V ol. C-32, No. 2,February, 1983.OBSTACLE EMPTY [6] Lumelsky, V . J., Mukhopadhyay, S., Sun, K., “Dynamic Path Planning in Sensor-Based Terrain Acquisition”, IEEE Transac-tions on Robotics and Automation, V ol. 6, No. 4, August, 1990.[7] Lumelsky, V . J., Stepanov, A. A., “Dynamic Path Planning for a Mobile Automaton with Limited Information on the Envi-ronment”, IEEE Transactions on Automatic Control, V ol. AC-31, No. 11, November, 1986.[8] Nilsson, N. J., “Principles of Artificial Intelligence”, Tioga Publishing Company, 1980.[9] Pirzadeh, A., Snyder, W., “A Unified Solution to Coverage and Search in Explored and Unexplored Terrains Using Indirect Control”, Proc. of the IEEE International Conference on Robot-ics and Automation, May, 1990.[10] Rao, N. S. V ., “An Algorithmic Framework for Navigation in Unknown Terrains”, IEEE Computer, June, 1989.[11] Rao, N.S.V ., Stoltzfus, N., Iyengar, S. S., “A ‘Retraction’Method for Learned Navigation in Unknown Terrains for a Cir-cular Robot,” IEEE Transactions on Robotics and Automation,V ol. 7, No. 5, October, 1991.[12] Rosenblatt, J. K., Langer, D., Hebert, M., “An Integrated System for Autonomous Off-Road Navigation,” Proc. of the IEEE International Conference on Robotics and Automation,May, 1994.[13] Samet, H., “An Overview of Quadtrees, Octrees andRelated Hierarchical Data Structures,” in NATO ASI Series, V ol.F40, Theoretical Foundations of Computer Graphics, Berlin:Springer-Verlag, 1988.[14] Stentz, A., “Optimal and Efficient Path Planning for Unknown and Dynamic Environments,” Carnegie MellonRobotics Institute Technical Report CMU-RI-TR-93-20, August,1993.[15] Zelinsky, A., “A Mobile Robot Exploration Algorithm”,IEEE Transactions on Robotics and Automation, V ol. 8, No. 6,December, 1992.。

快速运动去模糊摘要本文介绍了一种针对只几秒钟功夫的大小适中的静态单一影像的快速去模糊方法。

借以引入一种新奇的预测步骤和致力于图像偏导而不是单个像素点，我们在迭代去模糊过程上增加了清晰图像估计和核估计。

在预测步骤中，我们使用简单的图像处理技术从估算出的清晰图像推测出的固定边缘，将单独用于核估计。

使用这种方法，前计算高效高斯可满足对于估量清晰图像的反卷积，而且小的卷积结果还会在预测中被抑制。

对于核估计，我们用图像衍生品表示了优化函数，经减轻共轭梯度法所需的傅立叶变换个数优化计算过数值系统条件，可更加快速收敛。

实验结果表明，我们的方法比前人的工作更好，而且去模糊质量也是比得上的。

GPU（Graphics Processing Unit图像处理器）的安装使用程。

我们还说明了这个规划比起使用单个像素点需要更少的更加促进了进一步的提速，让我们的方法更快满足实际用途。

CR（计算机X成像）序列号：I.4.3[图像处理和计算机视觉]：增强—锐化和去模糊关键词：运动模糊，去模糊，图像恢复1引言运动模糊是很常见的一种引起图像模糊并伴随不可避免的信息损失的情况。

它通常由花大量时间积聚进入光线形成图像的图像传感器的特性造成。

曝光期间，如果相机的图像传感器移动，就会造成图像运动模糊。

如果运动模糊是移位不变的，它可以看作是一个清晰图像与一个运动模糊核的卷积，其中核描述了传感器的踪迹。

然后，去除图像的运动模糊就变成了一个去卷积运算。

在非盲去卷积过程中，已知运动模糊核，问题是运动模糊核从一个模糊变形恢复出清晰图像。

在盲去卷积过程中，模糊核是未知的，清晰图像的恢复就变得更加具有挑战性。

本文中，我们解决了静态单一图像的盲去卷积问题，模糊核与清晰图像都是由输入模糊图像估量出。

单一映像的盲去卷积是一个不适定问题，因为未知事件个数超过了观测数据的个数。

早期的方法在运动模糊核上强加了限制条件，使用了参数化形式[Chen et al. 1996;Chan and Wong 1998; Yitzhaky et al. 1998; Rav-Acha and Peleg2005]。

Put Your Lab InMotion™Flexible and EfficientA u t o m a t i o nInMotion ™ Autosamplers Flex ProMax2Put Your Lab InMotion™Flexible and Efficient AutosamplersAutomation in a laboratory today has high demands for a variety ofsamples and workflows. Automation is no longer just going from sample to sample for analysis. From eliminating process order and transcription errors of sample information to complex cleaning and environmental control and protection for analysis, our autosamplers are designed to assist in every way for flexible workflows and efficient analysis.I n M o t i o n A u t o s a m p l e r s3Put your lab in motion to work for you.4P r o d u c t i v eMaximum Productivity in Minimal SpaceEngineered to increase productivity without sacrificing laboratory bench space, InMotion ™ Autosamplers are a fit for any lab. Designed to go ver­tical and not horizontal, accessories and components are stacked next to the towers or inserted into the main housing saving further space as your instrument is expanded.5Stay productive with true high throughput analysis.6Flexible Automation to Suit Your WorkflowThe open programming of our instruments coupled with the flexibility of the InMotion ™ Autosamplers makes matching workflow processes easy. Advanced solvent addition, rinsing, draining and conditioning are intuitive and simple to program. Clever automation sequences can be programmed to perform two tasks simultaneously, truly increasing productivity by preparing your sample while testing another.One quick glance at the LED in-dicator light on the top of towers lets you know if your analysis is still running, needs your at-tention or is ready to run more samples. Be productive on the go. Use LabX ® to email results or a message to let you know your analyses are finished and more samples can be loaded.Stay connected with a glanceF l e x i b l eRest assured your testingcomponents are clean andready from the first sampleto the last.78M o d u l a r a n d T a i l o r e dModular and Tailored for Your SamplesInMotion ™ Autosamplers can be tailored for your samples. Titrating or measuring is just a part of your process. Make sure your conditions are met with our wide range of sample specific accessories suited for your analysis. Build the system to meet your needs; no more and no less than what is needed with our modular systems built to your analysis.9Read, temperate, cover and uncover your samples as you would manually.10S m a r t S a m p l e™Secure and EfficientWeighing of Titration SamplesGain the ultimate efficiency and security weighing titration samples with SmartSample ™. This optimized workflow allows for all sample information to be entered at the Excellence Balance with the SmartSample kit while weighing. Eliminate back and forth workflows, transcription errors and no longer worry about placing your samples on the rack in the wrong order.11Use the latest in RFID technology to program and store your sample information with the sample. Watch and learn how SmartSample works at /SmartSample12D e n s i t y , R e f r a c t i v e I n d e x & M o r eElegant and Thorough Automation with Multiparameter AnalysesTruly maximize the productivity offered by InMotion ™ with multiple tests for one sample. In addition to offering the intuitive and simple to useOne Click ® interface for all of our analytical laboratory instruments, we also offer one common autosampler. The InMotion Autosamplers not only connect to Excellence Titrators, but also to our LiquiPhysics ™ Excellence density meters and refractometers, SevenExcellence ™ multiparameterbenchtop meter, and UV/VIS spectrophotometers. Combine instruments for ultimate efficiency in your lab making your own multiparameter system.Easily determine pH and Brix in juices with the addition of aSevenCompact ™ pH meter to your density meter or refractometer. Thoroughly mix the juice with the Compact Stirrer while measuring pH and before transferring to the LiquiPhysics instrument. De-gasing of carbonated beverages is simple and efficient.Combine instruments in-line with the InMotion Autosamplers for multiparameter analyses, e.g. °Brix, acidity and pH in bever-ages. Directly measure potential of samples, send the samples to other instruments before or after dilution while automatically tak-ing sample aliquots for titration.With the PowerShower ™, a single click on the touchscreen thor-oughly cleans the whole system between sample series. Automat-ically park the pH electrode in the proper storage solution when sample analysis is complete.°Brix and pH in beverages Easy to use and versatile Multiparameter analysis13Optimize your lab’s productivity.Refractometer Density Meter InMotion Autosampler connects to:Titrator pH Meter UV/VIS14A c c e s s o r i e sClever Automation Accessories for Tailored SolutionsBuild the right automation solution for your laboratory using our wide range of specific and tailored accessories to meet all aspects of your sample analysis requirements.Flex, Max and Pro 100 mL RacksBase Number of Samples Beaker Size (mL)Flex50252780181001518011250Pro1822569803410023180Max3032511380551004318024250Water Bath Flex 18100Pro618029100Racks* Not with Water Bath Racks / ** Not with 25 mL RacksInstrumentBase ModelFeature Titration Excellence Density Meters and Refractometers UV/VIS Seven Excellence Flex ProMaxAdditional Tower Yes ---Yes (not with 25 mL Racks)PowerShower Yes Yes Yes Yes Yes Yes Yes Line Rinse/Rinse Yes Yes Yes -Yes Yes Yes Conditioning Yes ---Yes Yes Yes Automated Sensor Park Yes Yes --Yes Yes Yes LED Status Light Yes Yes Yes Yes YesYesYesStirrer/Pump Ports 2 to 6 2 to 4 2 to 4 2 to 6 2 ( expandable to 6)SmartSample*/** Yes ---Yes Yes (outer 2 rows)-Barcode Reader (1D and 2D) */**Yes Yes Yes (with LabX)Yes Yes Yes (outer row)-Aliquot Kit Yes ----Yes (25 mL Rack)-Chemical Oxygen Demand Kit Yes ---Yes --Karl Fischer Kit Yes ---Yes Yes -Water Bath Rack Yes Yes Yes Yes Yes Yes-Magnetic Stirrer*Yes Yes Yes -Yes Yes (outer 2 rows)-Compact StirrerYes--YesYes YesYes15PumpsSD660 Membrane SP280 PeristalticSPR200 Reversible Peristaltic Solvent ManagerKitsSmartSample ™CoverUp ™Karl Fischer Aliquot CODLiquid Sampling Liquid Handler TV6 Valve Stirrers Compact Overhead Magnetic, Undermount Option BoardsCoverUp / Stirrer / Pump Barcode / SmartSampleAccessoriesSevenExcellence pH meter with InMotion Flex, RM40 Refractometer with InMotion Pro and T9 Titrator with InMotion Max.SPR200 PumpBarcode / SmartSample Option BoardKarl Fischer KitLiquid Handler LabX ® PC Software SmartSample Tags and SleevesChemical Oxygen Demand Kit/InMotionFor more informationMake operations simple and universal in your laboratory with our fleet of instruments and balances.Titration ExcellenceThe intuitive user interface and One Click ® operation make titrations and manual operations fast and simple on our Excellence Titrators. Secure your analyses with detailed user management, Plug & Play sensors, bu-rettes and peripherals. Build the titrator for your needs today, and tomorrow, with our multitude of modular accessories.LiquiPhysics ™ ExcellenceThe multitalented LiquiPhysics system reliably mea-sures density, refractive index and related values such as °Brix, HFCS, alcohol concentrations or API gravity. It can be automated and upgraded to multiparameter systems for simultaneous deter m ination of additional parameters such as pH / conductivity, color, acidity and more.SevenExcellence ™ multiparameterWith this professional meter for the determination of pH, conductivity, redox potential, ion concentration and dissolved oxygen, a parallel measurement of up to three channels is possible. SevenExcellence stands for high performance, safe results and solid compli-ance. Via the LabX software it can be connected to the InMotion sample changer.InMotion KF Oven AutosamplersModern and extremely compact, the new InMotion KF Oven Autosamplers allows up to 26 samples to be placed on a rack of only 25 centimeters. The Tempera-ture Scan functionality speeds up the analysis of unknown samples by determining, in just one single run, the optimum temperature for heating the sample.Intuitive and UniversalOne Click is a Registered Trademark of METTLER TOLEDO in Switzerland, the European Union, Russia and bX is a Registered Trademark of METTLER TOLEDO inSwitzerland, USA, China, Germany and a further 13 countries.METTLER TOLEDO Group Laboratory DivisionLocal contact: /contactSubject to technical changes© 06/2017 METTLER TOLEDO. All rights reserved.30100369AMarketing Titration / MarCom Analytical。

motion trajectory fields -回复Motion trajectory fields是指运动轨迹场，在计算机视觉和计算机图形学领域应用广泛。

它们可以用于识别运动物体的轨迹、分析运动模式和预测物体未来的运动路径。

在本文中，我将一步一步回答一些关于motion trajectory fields的问题，并介绍它们在不同领域的应用。

首先，什么是motion trajectory fields？motion trajectory fields是描述运动物体在空间中的轨迹和运动方向的数学模型。

它们通过分析运动物体在连续时间段内的位置变化，确定物体的运动路径和速度。

其次，motion trajectory fields是如何计算的？计算motion trajectory fields的一种常见方法是使用光流估计技术。

光流估计是通过分析图像序列中相邻帧之间的亮度变化来计算物体的运动模式。

这可以通过追踪像素的灰度值变化或特征点的移动来实现。

根据这些运动信息，可以生成运动轨迹场。

然后，motion trajectory fields的应用有哪些？motion trajectory fields在很多领域都有广泛的应用。

在计算机视觉领域，它们被用于目标跟踪、行为分析和物体识别。

例如，在目标跟踪方面，可以通过观察运动物体的轨迹来确定其位置和速度，从而实现精确的跟踪。

在行为分析方面，利用运动轨迹场可以识别和分析人的动作模式，如散步、跑步或跳跃。

此外，motion trajectory fields也被应用于虚拟现实和增强现实中，为用户提供更真实的交互体验。

最后，motion trajectory fields的未来发展方向是什么？随着计算机视觉和计算机图形学技术的不断进步，motion trajectory fields的应用潜力也在不断扩大。

未来的发展方向可以包括更精细的运动分析和预测，以及更高效的计算算法。

motion blur算法
Motion blur（运动模糊）算法是一种用于模拟快速运动物体在图像中留下的模糊效果的图形处理技术。

这种算法通常用于电影、视频游戏和计算机图形中，以增加真实感和动态感。

Motion blur 算法的基本原理是通过模拟物体在相机快门打开期间的运动轨迹，从而在图像中产生模糊效果。

在图形学中，实现motion blur的算法有很多种。

其中之一是基于物体速度的线性插值。

这种方法通过计算物体在相机快门打开期间的位置变化，然后在图像中对这些位置进行插值，从而模拟出模糊效果。

另一种常见的方法是基于运动模糊核的卷积滤波。

这种方法通过将图像与特定的运动模糊核进行卷积操作，从而实现模糊效果。

除了这些基本的方法外，还有一些高级的motion blur算法，如基于矢量运动模糊的算法。

这种算法可以更准确地模拟物体在图像中的运动轨迹，并产生更真实的模糊效果。

此外，还有一些基于深度信息的motion blur算法，可以根据物体的深度信息对模糊效果进行调整，以增加真实感。

总的来说，motion blur算法是一种重要的图形处理技术，可以用于增加图像和视频的真实感和动态感。

它有许多不同的实现方式，每种方式都有其特点和适用场景。

在实际应用中，开发人员需要根据具体的需求和场景选择合适的motion blur算法来实现所需的效果。

电气传动2024年第54卷第1期ELECTRIC DRIVE 2024Vol.54No.1摘要：我国老龄人群肢体障碍者很多，运动康复技术是康复治疗的有效手段。

但医患比例严重失调难以使得人人都能享受到康复医疗服务。

康复机器人通过阻抗控制技术能够与人体进行一定的安全交互，但现有康复机器人多采用定阻抗控制，环境适应能力弱，难以应用于临床。

针对上述问题，提出一种变阻抗控制方法，以采集使用者的表面肌电信号为输入条件，通过改进随机森林算法训练识别使用者上肢的运动角度。

并配合末端力传感器，获得使用者的运动意图，再通过变阻抗控制器完成康复运动。

搭建了实验平台，并对轨迹跟踪和康复训练能力进行验证与评估。

结果表明所设计的控制器能够控制机器人完成康复运动。

关键词：康复机器人；表面肌电信号；改进随机森林算法；变阻抗中图分类号：TP13文献标识码：ADOI ：10.19457/j.1001-2095.dqcd24614Research on Variable Impedance Control Technology of Upper Limb Rehabilitation Robot Based on sEMGWU Tong 1，LI Jian 1，LI Guodong 2，LIU Lu 1，ZHU Liguo 3，FENG Minshan 3（1.Automated Institute ，Beijing Institute of Technology ，Beijing 100089，China ；2.China Software Testing Center ，Beijing 100089，China ；3.Beijing Key Laboratory of Traditional Chinese Medicine Orthopedic Technology ，Wangjing Hospital of China Academy of Chinese Medical Sciences ，Beijing 100020，China ）Abstract:There are many elderly people with limb disorder in China ，and exercise rehabilitation technology is an effective means of rehabilitation treatment.However ，the serious imbalance of doctor-patient ratio makes it difficult for everyone to enjoy rehabilitation medical services.Impedance control technology is used for the safe interaction between rehabilitation robot and human body.However ，constant impedance control is used in the existing rehabilitation robots ，which has weak environmental adaptability and is difficult to be applied in clinical practice.In view of the above problems ，a variable impedance control method was proposed.The user's surface electromyography signal （sEMG ）was collected as input ，and his upper limb motion angle was trained and recognized by the improved random forest algorithm.With the end force sensor ，the motion intention was obtained ，and then the rehabilitation motion was completed by the variable impedance controller.The experimental platform was built ，and the track tracking and rehabilitation training abilities were verified and evaluated.The results show that the designed controller could control the robot to complete rehabilitation movement.Key words:rehabilitation robot ；surface electromyography signal （sEMG ）；improved random forest algorithm ；variable impedance基金项目：国家中医药管理局中医药创新团队及人才支持计划项目（ZYYCXTD-C-202003）；北京理工大学实验室研究项目（2019BITSYA14）；中国中医科学院科技创新工程《腰椎扳动类手法教学培训系统的研发》（C12021A02014）作者简介：吴彤（1997—），男，本科，Email ：通讯作者：李国栋（1984—），男，博士，工程师，Email ：基于表面肌电信号的上肢康复机器人变阻抗控制技术研究吴彤1，李健1，李国栋2，刘路1，朱立国3，冯敏山3（1.北京理工大学自动化学院，北京100089；2.中国软件测评中心，北京100089；3.中国中医科学院望京医院中医正骨技术北京市重点实验室，北京100020）我国目前由疾病导致的运动功能障碍人数较多[1]，但专业的康复医师数量有限，因此更多要依赖康复机器人提供康复训练[2]。

图像去噪是计算机视觉领域的一个重要问题，它在图像处理和模式识别领域有着广泛的应用。

而堆叠自动编码器是一种深度学习模型，能够有效地应用于图像去噪任务。

本文将介绍如何使用堆叠自动编码器进行图像去噪的方法和技巧。

首先，我们需要了解什么是自动编码器。

自动编码器是一种神经网络模型，它能够学习输入数据的有效表示，并通过学习到的表示来重建输入数据。

它通常由一个编码器和一个解码器组成。

编码器将输入数据映射到一个低维的表示空间，而解码器则将这个表示空间映射回原始的输入数据空间。

堆叠自动编码器是由多个自动编码器堆叠而成的深度学习模型，它能够学习更加复杂和抽象的表示。

在使用堆叠自动编码器进行图像去噪时，我们首先需要准备带有噪声的图像数据集。

这个数据集可以包含各种类型的图像，例如自然图像、人工图像等。

接着，我们需要设计一个合适的堆叠自动编码器架构，以便能够学习到图像的有效表示，并且能够对噪声图像进行重建。

通常情况下，我们可以选择使用卷积自动编码器作为堆叠自动编码器的基本单元。

卷积自动编码器能够有效地捕捉图像中的局部特征，并且能够减少参数的数量，从而提高模型的泛化能力。

在设计堆叠自动编码器架构时，我们可以采用多层卷积自动编码器，并且在每一层之间使用池化操作来降低特征图的维度。

接下来，我们需要选择合适的损失函数来衡量堆叠自动编码器的重建性能。

对于图像去噪任务来说，我们可以选择均方误差（MSE）作为损失函数。

MSE能够衡量重建图像与原始图像之间的差异，从而能够有效地指导模型学习到更加准确的表示。

在训练堆叠自动编码器时，我们可以选择使用反向传播算法和随机梯度下降（SGD）优化器来最小化损失函数。

反向传播算法能够有效地计算损失函数对模型参数的梯度，而SGD优化器能够根据梯度的方向来更新模型参数，从而不断优化模型的性能。

另外，为了提高堆叠自动编码器的去噪性能，我们还可以采用一些正则化技术，例如dropout和批标准化。

dropout能够随机地丢弃一部分神经元的输出，从而能够减少模型的过拟合现象；批标准化能够加速模型的收敛速度，提高模型的训练效率。

无人机地面站（GCS）Mission Planner 操作使用手册小左实验室2014-10-1目录Mission Planner 操作使用手册 (1)1.Mission Planner简介 (2)2.Mission Planner安装 (2)3.飞控板固件加载 (3)4.链接飞控板 (5)5.Mission Planner显示面板及特点 (5)5.1连接Connect (5)5.2飞行数据Flight Data (5)5.3飞行规划Flight Planning (7)5.4初始化设置Initial setup (7)5.5参数配置和调整Params Configure安定tuning (7)5.6仿真器 (8)6飞行任务规划 (8)6.1航点规划及动作 (8)6.2任务指令参考 (10)6.3相机控制与自动操作 (11)6.4转场点设置 (13)6.5地形跟踪 (15)7.基于数据记录的故障诊断 (16)7.1基于logs诊断问题 (16)7.２数传电台记录诊断 (20)7.３闪存数据记录 (22)7.４记录数据与回放任务 (25)7.５振动测量分析 (26)8.开源Mission Planner的二次开发基础 (29)8.1Visual Studio Community 13.0打开Mission Planner solution (29)8.2 发布修改后的Mission Planner (31)11.Mission Planner简介Mission Planner是无人机地面控制站软件，适用于固定翼，旋翼机和地面车。

仅仅在windows 系统下工作。

Mission Planner可给你的自动车辆提供配置工具或动力学控制。

其主要特点：●给控制板提供固件加载●设定，配置及调整飞行器至最优性能●通过在地图上的鼠标点击入口来规划，保存及加载自动任务给飞控板●下载及分析由飞控板创建的任务记录●与PC飞行模拟器连接，提供硬件在环的UAV模拟器●通过适当的数传电台，可以监控飞行器状态，记录电台传递数据，分析电台记录或在FPV模式下工作2.Mission Planner安装Mission Planner是windows系统上的自由开源软件，安装非常简单。