We are developing a surgical support system for a liver laparotomy surgery. In our system, we aim to navigate the surgical tools during surgery adapted to the change of the position, orientation and deformation of the liver during operation. The position and orientation of the liver is measured by matching the surface shape of the real liver measured by depth camera and the depth image generated from the 3D model of the liver. In this paper, we present a fast depth image generation method from computed tomography images (DICOM) using a general-purpose computing on graphics processing units (GPGPU). The experiments and results to estimate the position and orientation of the liver from the generated DICOM depth image and the depth image of a real liver model acquired from a depth camera are also described.

In this paper, we model a rheology object whose main characteristic is the existence of residual displacement. In order to speed up calculation, to keep the stability, and also to control the residual replacement, we adopt MSD (Mass-Spring- Damper) voxel-lattice model and calibrate their physical parameters by using differences against experimentally captured shapes. In general, a human operator manipulates the MSD model by the most popular graphics software OpenGL and force feedback device PHANTOM in a 3-D CG environment. In order to get wonderful visual and tactile realities, we need force and shape calculations less than a couple of 10 milli-seconds. For saving computational cost, we propose the octree-based MSD model. Based on several experimental and comparative results, we check whether twin goals such as efficiency of calculation time and precision of shape deformation are compatible or not in the octree-based MSD model.

In this paper, we precisely discuss two necessary methods to manipulate artificially a rheology object by another rigid object via force feedback (haptics) devise. The rheology object is quite popular material in our living life, e.g., food materials such as several kinds of noodles, human bodies such as organs and muscles, and an article of clothing. For this reason, it is very important for us to manipulate a rheology object by another rigid object. In our previous works, we finish modeling and calibrating MSD rheology model. Therefore, in this paper, we define some collision model to make and calibrate a set of external forces based on the swept volume of rheology object by rigid body. Also, we revisit some force transformation method between encountered surfaces of rheology object and rigid body. In this research, we successively regard both methods as penalty method and bilinear approximation method

In this paper, we propose an experimental impulse-momentum-based approach to make artificially discrete impulses between rigid bodies with multiple contacts. It is impossible for us to sense precisely impulsive waves between such bodies. For this reason, we calibrate each impulsive distribution of encountered bodies by minimizing the differences of their momentum variations in real and virtual dynamic simulations. If number of contact point is one, we can distinguish vertical and horizontal planes at the contact in each local coordinate system. Therefore, an uncertain parameter set (width and height of impulse, and coefficient of restitution) of vertical impulse and the other set (static and kinetic friction coefficients) of horizontal impulse are individually calibrated. However, if the number is more than two, they should be simultaneously calibrated along X, Y, and Z axes of the global (absolute) coordinate system. Furthermore in order to get more precise multiple impulses, we successively calibrate impulse transmission ratios of two or more contacts between three or more bodies. Finally, by comparing artificial and experimental dynamic simulations, we ascertain feasibility of our impulse-momentum-based approach.

A rheology object means a visco-elastic object with some residual displacement. The modeling is useful to manipulate a real rheology object by a robot hand/arm or to feel a contact impulse (forces) from a virtual one by some haptic device. In our previous works, we compared several types of MSD models with/without two kinds of conservation laws of volume by giving position replacements at some surrounding masses, calibrating and evaluating shape differences between virtual and real rheology objects. Concerning to shape precision, the combination is wonderful. Also, the model including conservation laws of volume is better than the model excluding them. However, concerning to force precision, they are unfortunately meaningless. To overcome this drawback in this paper, we compare the types of MSD models by giving, calibrating and evaluating impulses and their differences at the masses around the virtual and real rheology objects. As a result, for the purpose, the new combination is suitable. Furthermore, concerning to force precision, the model excluding conservation laws of volume is better than the model including them.

In many sensor-based path-planning algorithms, the worst path length has been theoretically evaluated, but the average path length will not be theoretically and experimentally evaluated at all. In general, shorting average path length is worth much than shorting worst path length in the practical use. Therefore, we propose a new sensor-based path-planning algorithm whose path length is exactly shorten on the average. The algorithm always expands the best crack of a spanned graph from an initial position. All cracks mean all tips of routes traced from hit and/or leave points and also all neighbors of hit and/or leave points not to trace. The evaluation and expansion work by A* in the spanned graph. By selection of the best node, a mobile robot frequently reverses its direction following an uncertain obstacle. For this reason, the robot frequently passes through a shorter interval around an unknown obstacle three times or more. As a result, the worst path length cannot be bounded as any small value. However, a total driving distance is completely saved by following a short boundary three times or more, which is faster than following a long boundary two times. In this paper, we ascertain the superiority of our algorithm experimentally by a huge number of unknown environments.

The MSD (Mass-Spring-Damper) model efficiently calculates shape deformation of many kinds of materials such as elastic, visco-elastic, and rheologic objects. For this reason, dynamic animation can be made in a personal computer and its popular acceleration board within the video-frame rate. The problem of MSD model is how to maintain shape precision of each deformation. For this purpose, we have calibrated coefficients of damper and spring of Voigt part and a coefficient of damper of the other part in the basic MSD element under many surface points capturing a real rheologic object by the randomized algorithm. Nevertheless, the shape precision is not unfortunately enough. To overcome this, we improve our previous approach in the following five points: (1) The number of voxels in the MSD model increases from 75 to 600. (2) The ratio between lengths of Voigt and the other parts in the MSD element is added to three coefficients of spring and dampers of the basic element as calibrating parameters. (3) Four unknown parameters of the basic element are distinguished to calibrate in and on each voxel. In addition, the parameters are distinguished to calibrate among surface and core areas of a virtual rheologic object. (4) In order to speed up the calibration, we use GA (Genetic Algorithm) in replace of RA (Randomized Algorithm). (5) Each or both of local and global volume constant conditions are added into the previous approach. In conclusion, we investigate relations between shape deformation, volume resolution, and number of calibrated parameters in several MSD models representing a rheologic object. Also, we improve deformation precision by increasing not only volume resolution but also number of calibration parameters or by adding each or both of volume constant conditions.

In this paper, we compare two major structures of MSD (mass-spring-damper) particle models. One is the lattice (hexahedral) structure, and the other is the truss (tetrahedral) structure. They (especially, the truss structure) have been frequently used for representing elastic and/or visco-elastic object. The MSD model efficiently calculates shape deformation of the above materials. In addition, in order to maintain shape precision of each deformation, we carefully calibrate coefficients of damper and spring of Voigt part and a coefficient of damper of the other part in the basic MSD element under many surface points capturing a real rheologic object. A genetic algorithm is used for probabilistic calibration. After the comparison, we get the following properties: (1) the lattice structure has too many elements for calculating force propagation. Therefore, it precisely leads shape deformation with the help of the local (feedforward) volume constant condition. (2) The truss structure does not have enough elements for propagating internal forces, therefore, in order to keep a reasonable volume by expanding its virtual rheology object, we need the global (feedback) volume constant condition. (3) The global condition is time consuming, but can directly control the total volume of virtual rheology object. On the other hand, the local one is quick, but directly expands only a part (voxel) of the virtual object. Therefore, the volume and shape in the lattice structure with the local condition are better than those in the truss structure including the global one. (4) The number of MSD elements in the lattice structure is about two times larger than that in the truss one. Therefore, the former calculation is about two times slower than the latter one. As contrasted with this, the global volume constant condition is strictly two times or slower than the local one. As a result, calculation time of the lattice structure with the local condition is smaller than that of the truss structure with the global one. In conclusion, the lattice structure with the local volume constant condition is the best concerning to calculation cost and shape precision.

There are many kinds of rheology objects in our living life. If such rheology objects are individually and completely modeled, we can flexibly deal with such various objects in a factory by a robotic manipulator controlling six degrees-of-freedom forces and moments and also operate them at a 3-D graphics world in a house by a human via a wonderful haptic device feeling the forces and moments. If such a system is developed after acquiring a rheology dynamic model, we can enjoy a clay work in a 3-D virtual environment. For this purpose, we calibrate deformation model of a rheology object by a modified randomized algorithm based on experimental data. The data is measured from a bread material pushed by a robotic manipulator exactly. The model is a 3-D voxel/lattice structure with many elements, and each element consists of two dampers and one spring. By changing three coefficients of dampers and spring, we can describe various material properties concerning to viscosity and elasticity. In this paper, by minimizing shape difference between real and virtual rheology objects in the near-optimal algorithm, we find a better set of coefficients. Using the calibrated model, we can feel three degrees-of-freedom forces and three degrees-of-freedom moments attracted from a calibrated virtual object in a haptic device and synchronously we can watch shape deformation of the object in a 3-D graphics animation.

In robotics, many path-planning algorithms have been proposed but almost all are evaluated only by their path lengths in PC. However, the evaluation is completely independent of a human ability. Recently, a human intends to live with many robots. For this reason, we should experimentally evaluate many kinds of interactions between a human and robots in our living space, which are supervised by each path-planning algorithm. Unfortunately, it is impossible, expensive and dangerous for us to investigate such interactions in a real world. To overcome such drawbacks, we propose wearable-based system to evaluate a path-planning algorithm by a human being. A human avoids some neighbors of virtual robots by using two eyes (using his visual property) and two legs (using his movable ability). In our wearable system, we can quickly develop smart robots and sensors without considering many irrational technical limitations. Therefore, we can test a novel sensor-based path-planning algorithm in the virtual environment. Using this, their superiorities are checked by visual and movable abilities of a human being.

Based on many large data set, we calibrate a near-optimal heuristic as a constant function for guiding efficiently A or A* algorithm. We claim that this magic number exists as a universal constant for several kinds of data sets. This is perhaps related to the nature of their data sets though it is not theoretically analyzed. In general A* and Dijkstra algorithms always pick up the optimal (e.g., the shortest) path between two nodes on a given graph. However, because they do not use any good heuristics, they spend much time to calculate. To overcome this drawback, we propose A of A* algorithm with a smart heuristics. The algorithm quickly investigates an optimal or near-optimal path. Unfortunately, the heuristics does not always maintain the admissibility, and thus our algorithm does not sometimes pick up the optimal path. Finally, we ascertain superiority of the proposed algorithm to the classic A* and Dijkstra algorithms by two kinds of extremely different data sets.

In the CG community, many kinds of physical-based (impulse-based) approaches such as Mirtich's and Baraff's have been proposed for showing dynamic animation. However, because they generate and calibrate only an impulsive force, i.e., an area of force distribution, the impulsive forces are not always precisely calibrated. Moreover, since they do not deal with any exact impulse (force distribution), they cannot be applicable for dynamic animation with simultaneous contacts between bodies and for tactile feedback display between them. In order to overcome such drawbacks, we proposed a new approach to generate an arbitrary impulse (force distribution) artificially based on practical time, and tried for dynamic animation with single contact between plastic puck and wall in an air hockey game. In this paper, we extend our proposed approach for a human to strike a puck by a mallet and to feel their impulse by a haptic device such as PHANToM. Moreover, we investigate impulse precision by changing penetration depth between puck and mallet.

In this paper, we propose a smart teaching system for many complex tasks achieved by a seven degrees-of-freedom robotic manipulator. In this system, we basically use a sliced 2-D configuration plane because of no occlusion. In general, an enormous number of such planes exist in seven dimensional configuration space. To select some fruitful planes from all the planes, we develop a human support system based on efficient path finding and obstacle evaluating algorithms in each 2-D plane. The efficiency of this human computer cooperation system is compared with that of the model-based path-planning algorithm A*. Selecting a near-optimal path in our system is absolutely faster than calculating its optimal path by A*. This means that a human ability understanding a task is quite powerful especially for a seven-degrees-of-freedom robotic manipulator.

The purpose of this research is to calibrate sets of kinematics and dynamic parameters of human arm or leg from its captured points via many behaviors. If both sets are successively identified, we can easily generate dynamic animation of human such as handling, pitching, walking, running and so on. In addition, we can straightforwardly touch a virtual arm or leg while feeling reactive force/moment by a haptic rendering (tactile feedback display). In robotics, many types of algorithms have been proposed for calibrating kinematics and dynamic parameters of robotic manipulator. They are meaningless for calibrating a human arm or leg as follows: (1) we do not know any control scheme and feedback gain. (2) we do not know any torque of each actuator. (3) we do not know any set of good initial parameters of kinematics and dynamics. To overcome these, we propose a probabilistic algorithm to calibrate sets of kinematics and dynamic parameters of a human arm or leg from its successive captured points. The calibration algorithm based on GA (Genetic Algorithm) does not require any set of good initial set of kinematics and dynamic parameters.

In this paper, we propose three types of sensor-based path-planning algorithms and compare them as the image-based path-planning algorithm for a huge search space. In the general image-based path-planning, a camera mounted on a tip of a manipulator is seeking for an objective image while the manipulator is controlled in a joint space. As long as the number of degrees-of-freedom of a manipulator increases, the search space becomes exponentially huge. Though the sensor-based path-planning algorithm is a noncombination search, it sometimes spends much time to escape from a valley minimized by a local minimum. To overcome this problem, we use a modified version of the randomized algorithm as the best image-based path-planning algorithm for a huge search space. This tendency is checked by several simulation results. In addition, the version can be easily applied for a real problem as the classic visual servoing (the steepest descendent method) with memorizing a set of visited points and another set of their neighbor points, as well as generating a sequence of random motions.

In this paper, we compare many kinds of randomized algorithms and simultaneously inspect their data to calibrate an impulse force between two rigid bodies. One is an object handled by a manipulator tip, and another is an object fixed in a 3-D environment. A real impulse is obtained from an experiment via a six degrees-of-freedom force/moment sensor mounted on a tip of a seven degrees-of-freedom manipulator. As contrasted with this, a virtual impulse is quickly calculated in our impulse model. It consists of two classic models. One is Hertz's contact force model and another is Coulomb's friction force model. Each of extended randomized algorithms always minimizes the difference between real and virtual forces in order to get a better impulse model. In general, the randomized algorithm works well if and only if a set of correspondences between practical (true) and virtual (false) forces has high quality. Therefore, we carefully evaluate the correspondences and eliminate a few bad ones. Since our impulse model is not so complicated, it can be well calibrated from a few but good correspondences.

In this paper, we calibrate Mirtich's approach (1996) for computing a collision impulse by two kinds of randomized algorithms, and then apply the model for an air hockey game. Mirtich proposed a smart dynamic simulation called impulse-based simulation. He considers twin goals of physical accuracy and computational efficiency. The simulation can accurately model complex dynamic system in real-time. However, whether his impulse-based model is reasonable or not has not been investigated at all by any experimental result. For example, his impulse model requires the dynamic friction coefficient /spl mu//sub D/ and the coefficient e of restitution in advance. However, they strongly depend on shape and material of colliding objects. Because of noise and error of sensing, it is difficult for us to measure the parameters exactly. For this reason, in this paper, we calibrate these by using two kinds of randomized algorithms based on many reductions of momentums before and after the collision. Each momentum (multiplying mass and velocity) can be easily obtained by measuring relative linear velocities and angular velocities before and after the collision. They are practically and easily measured by a smart imaging of two objects. The air hockey game designed consists of two PC with two joysticks including force feedback, which are connecting each other by the fast Ethernet.

In this paper, we propose a feasible method to construct a virtual manipulator in a 3D graphics environment, which is equivalent to a real manipulator including its dynamics. For this purpose, we first calibrate the parameters of robot dynamics by the two classic algorithms. Unfortunately, both the classic methods are not practically stable because each motion pattern includes noise and error. To overcome this drawback, we indirectly absorb the position differences between experimental and calculated manipulators by three types of learning trees. Moreover, many neighbor dynamic motions are directly memorized by the same learning trees. As a result, when real and virtual robots are independently supervised by the PD control, their angular errors of rotational joints amount to zero. In addition, even though both robots are independently supervised as slave arms from a master arm by the same sequence of forces in a bilateral control based on the PD control, motion sequences of real and virtual slave arms equal to each other. As a result, a virtual manipulator can be used in a 3D graphics animation, which is truly replaced of a real manipulator.

As the sensor-based path-planning algorithm whose upper bound of path length is the smallest, Alg1 and Alg2 have been well known. In these algorithms, after encountering a visited point (that is, enters into a loop), a mobile robot follows an uncertain obstacle by an opposite direction until it can leave the obstacle. We call this as the "reverse procedure". Independently, if a robot always changes a direction following an uncertain obstacle alternatively, the robot arrives at a destination earlier on average (a probability for the robot to join a loop around a destination decreases). We call this as the "alternative following". In this paper, by mixing the reverse procedure and alternative following, we design new sensor-based path-planning algorithms Rev1 and Rev2. The upper bound 2D+2/spl Sigma//sub i/P/sub i/ in Rev1 and Rev2 is slightly longer than the upper bound D+2/spl Sigma//sub i/P/sub i/ in Alg1 and Alg2 (P/sub i/: the perimeter of an i-th encountered obstacle, D: the Euclidean distance between start and goal points). However, the average bound of path lengths in Rev1 and Rev2 will be shorter than that in Alg1 and Alg2. The former is fortunately evaluated by mathematical proofs, but the latter is unfortunately ascertained by several simulation results.

To design an image-based path-planning algorithm, we should decrease the sum of moving distances of degrees-of-freedom of a manipulator. The algorithm A* selects the shortest path in the joint space by hard search. The combination search requires long distance moving. In a computer (virtual) world, the moving is not always time consuming. However in a real world, the moving is extremely time consuming. To overcome this drawback, we are seeking for a one-way search. For this reason, the sensor-based path-planning algorithms are preferred to an image-based path-planning algorithm. On the observation, we adopt a three or more dimensional sensor-based path-planning algorithm as the image-based path-planning algorithm. Its heuristics is defined by a difference between present and objective images. If the heuristics amounts to zero, the image-based algorithm stops. Therefore, convergence of a camera on a manipulator tip to an objective state is kept, and it is not influenced at all by uncertainties of robot and camera parameters.

To achieve an assembly task in a teleoperation, a human operates a slave robot indirectly via a master robot, which are far from each other. The major problem of a teleoperation is how to overcome a transmission delay between a master robot at an operation site and a slave robot at a remote site. To solve this, we use virtual visual and tactile realities in an operation site and sensor-based motion-planning in a remote site. In the operation site, we construct a virtual environment approximating a remote site and then an operator selects a good sequence of motions for a virtual slave manipulator by a master manipulator. Unfortunately, the virtual environment is not equal to a remote site, and therefore motion gaps between virtual and real slave manipulators occur To overcome this, a slave robot absorbs the gaps by sensor-based motion-planning in the remote site. Finally, feasibility and robustness of our teleoperation system are ascertained by experiments based on master and slave manipulators and a 3D graphics workstation.

We propose an octree-based collision check algorithm EDGE for multiple manipulators with many degrees-of-freedom. The manipulator consists of many links, and therefore it should plan a collision-free sequence of motions by a collision check between two moving 3D links. In previous octree-based algorithms, we drop each patch of an object on an octree of another object to investigate their collision. In our proposed algorithm, we drop each edge of an object on an octree of another object to find the collision. With our algorithm, tracing the edge is much faster than covering the patch on the octree. For this purpose, we first develop an efficient algorithm for finding neighbor nodes (cubes) along an edge in an octree. Next, we build a collision check algorithm with the support of the neighbor finding algorithm.

In general, an unknown maze has few collision-free paths to a destination. Therefore, a robot supervised by the classic sensor-based path-planning algorithms Bug2, Class1, Alg1, Alg2 repeatedly enters into long local and global loops excluding and including a destination (goes out of its true way), respectively. For example, in Alg1 and Alg2, we can point out a case that a robot always enters into a global loop one time, and also in Bug(alter.) and Class1(alter.), we can find another case that a robot frequently joins a local loop many times. A complicated maze usually includes such cases, and therefore a robot arrives at a destination via a very long collision-free path. To overcome this, we revisit an algorithm, HD-I, whose following direction is adequately changed by trial and error. In HD-I, a robot hardly selects an inadequate direction and consequently decreases a probability to enter into global and local loops.

We propose sensor-based path-planning algorithms for a nonholonomic mobile robot. A car-like robot supervised by these algorithms always reaches its target point (position, and orientation) globally while sensing and avoiding uncertain neighbor obstacles locally in a 2-D environment. In general, all the classic sensor-based path-planning algorithms lead a robot to its destination (x,y) quickly in a 2-D unknown search space. Unfortunately, a nonholonomic mobile robot has three degrees-of-freedom (z,y,/spl theta/), and consequently its search space has three dimensions. In this paper, we propose two algorithms NH-I/spl middot/II. NH-I is designed by mixing modified versions of a famous model-based algorithm best-first and the classic sensor-based algorithm Class1. NH-II is designed by mixing modified versions of another famous model-based algorithm depth-first and Class1. BF and DF can investigate around an unknown obstacle whose dimensions are over two. As a result, by the mixture, we obtain three dimensional or more sensor-based path-planning algorithms NH-I/spl middot/II for a nonholonomic mobile robot. Finally, in order to check a real-time property of both algorithms, we compare their search costs with that of a model-based path-planning algorithm A/sub NH/* for a nonholonomic mobile robot.

We focus on how a mobile robot selects its direction to follow an encountered obstacle. For this purpose, in an uncertain 2D environment with simple shape, we propose new sensor-based navigation algorithms Simple(Class1) and Simple(Bug2) based on classic algorithms Class1 and Bug2. Moreover, in order to show a near-optimality of the proposed algorithms, we determine a competitive ratio r/sub 1/=(path length selected by Simple(Class1))/(the shortest path length selected by the model-based path-planning), and also determine a worst ratio r/sub 2/=(path length selected by Class1/(path length selected by Simple(Class1)). Also, we determine a competitive ratio r/sub 1/=(path length selected by Simple(Bug2))/(the shortest path length selected by the model-based path-planning), and also determine a worst ratio r/sub 2/=(path length selected by Bug2)/(path length selected by Simple(Bug2)). Since the competitive ratio r/sub 1/ is bounded by a small finite value, the new algorithms are regarded as near-optimal algorithms. On the other hand, since the worst ratio r/sub 2/ is determined by a large finite valve or infinite, the new algorithms are greatly improved against the classic algorithms.

A tangential graph has been widely used for selecting an optimal (shortest) path in a 2D environment with polygonal obstacles. The searching is very efficient because the size of a tangential graph is extremely small. However, it is difficult to design a smart method for constructing the graph in a 2D or 3D environment with free shaped obstacles. We firstly define a configuration space of a robotic manipulator as a 2D or 3D digital map, secondly construct a digital tangential graph in the map, and finally, select an optimal path from the graph by an A* algorithm. The size of a digital tangential graph and the speed of its A* search are ascertained by 2D and 3D graphics simulations.

To design an online or sensor-based path-planning algorithm, we should decrease its search cost (the number N of visited points of a robot in a known map or the sum S of moving distances of it in an uncertain map). For this purpose, the optimal algorithm, e.g. an A* algorithm is not suitable. Because in order to select an optimal path between start and goal points, the algorithm requests a huge set of visited points or driving distances. On the observation, by decreasing the sum S, we design a new sensor-based path-planning algorithm HD-I. In almost all the sensor-based algorithms, e.g. Class 1, convergence of a robot to its goal is ensured by decreasing the distance. Also in a famous algorithm, best-first (BF), the convergence is also kept by visiting a node whose distance to its goal is the smallest. They are similar because a robot does not take a distance from a start into account. Therefore, their modified versions can be mixed. Especially, BF can investigate around an unknown obstacle whose dimensions are over two. As a result, by mixing modified BF and Class 1, we obtain a three or more dimensional algorithm HD-I.

We propose a near-optimal sensor-based motion-planning algorithm for parts mating. In part mating, only a deadlock-free path to a target point exists around the configuration space obstacle of a point robot. Because the number of unknown obstacles is only one, our algorithm is able to seek for a complicated deadlock-free path efficiently, whose upper bound of the worst path length is exactly evaluated by p+2D (p: the perimeter of the configuration space obstacle; and D: the Euclidean, distance between initial and target points). In this type of sensor-based motion-planning, the lower bound of the worst path length is described by p+D. On the other hand, an upper bound of the worst path length was given by 1.5p+D in the previous algorithm Bug1, and also it was obtained by 2p+D in the previous algorithms Alg1 and Alg2. Comparing our new algorithm with these previous algorithms, if D is fully smaller than p, we ascertain our algorithm's superiority theoretically and experimentally. The proposed algorithm is a significant algorithm because there is only a configuration space obstacle for practical parts mating.

In the last decade, many sensor-based navigation algorithms have been proposed. In the sensor-based navigation, a robot arrives at its goal globally while avoiding neighbor obstacles locally by sensor information. In every environment, a mobile robot arrives at its goal surely. However if an environment has complicated shape, a mobile robot sometimes joins a loop and consequently runs long until its goal. In general, a loop consists of routes which a robot follows obstacles in the same direction. Nevertheless in most previous algorithms, a mobile robot follows an encountered obstacle in a constant direction. On this observation, a robot is exempted from participation of a loop by reversing a direction to follow an obstacle. The authors discuss algorithms in which the following direction is alternatively changed. This strategy has been adopted by cockroaches living in a natural environment. They then propose algorithms in which the following direction is randomly reversed. Then they compare paths generated by constant, alternative, and random selections in Bug2 and Classl under a graphics simulator for 2D complicated environments.

We discuss a bridge between model-based and sensor-based path-planning for a mobile robot in the presence of a self-positioning error. A model-based path-planning algorithm usually selects an arbitrary deadlock-free path in a computer world and then a mechanical vehicle faithfully follows the path in a real world. However if and only if the vehicle misunderstands its self-position by slipping and dead reckoning errors, it occasionally meets an unexpected obstruction since a selected path is to avoid all obstacles. As a result, the mechanical vehicle immediately falls into a deadlock in a real world. To avoid an unexpected obstacle in a real world, the vehicle obliges to use an online sensor-feedback function. However if the vehicle depends upon a careless sequence of online behaviors, it will join another deadlock, i.e., aperiodic sequence of online behaviors. To overcome this drawback, we propose three kinds of online bridges in order to generate the deadlock-free sequences of online behaviors along the path selected in an off-line path-planning algorithm.

In this paper, we propose a new type of two sensor-based path-planning algorithms running in a 2D uncertain world. In almost all previous sensor-based path-planning algorithms, the automaton comes close to the goal asymptotically when it leaves an obstructed obstacle. Consequently there is no obstacle where the automaton can hit in future at worst and then the automaton arrives at the goal finally. As a result, the proposed algorithms ensure their deadlock-free characteristics in an unknown world. As contrasted with this, the new type of two sensor-based path-planning algorithms ensures its deadlock-free characteristic by using several topological characteristics of an unknown world. Some of them are used for eliminating any local loop and alternatively the others are used for converging all global loops to the goal monotonously in an online manner. In result, even if the automaton encounters many global loops in an uncertain world, it finally catches the goal after leaving their minimum loop.>

An online path-planning algorithm for multiple automata is proposed. Each automaton usually goes straight to the goal. When some of the automata touch each other, some kind of swarm occurs and is identified by sensors. In general, several kinds of swarm appear, since a lot of automata collide in different circumstances. The proposed algorithm decomposes all simple and complex swarms uniformly by the following dynamic/static conversion: some automata are stopped in the swarm, and the others are moved around the set of stopped automata. By using this conversion, the algorithm destroys all swarms by some simple motions in common and is easily applied for some practical robots. Moreover, the automata decompose the swarm by cooperative motions as follows: an inside automaton comes close to its goal monotonously. Since all automata go straight to their goals outside the swarm, convergence of the automata toward their goals is naturally ensured. Communication overhead is kept small enough by using the monotony property, and consequently the algorithm can run online.

Proposes a new sensor-based path-planning algorithm running in an uncertain 2D world. In the algorithm, the automaton basically goes straight to the goal, and if it touches some uncertain obstacles, it traces the obstacle boundary until it can go straight to the goal again. Moreover if the automaton finds some loop in the world, it enters into the goal area. As a result, several loops encountered by the automaton become smaller monotonously in the world, and then the automaton arrives at the goal after it has escaped from the minimum loop. This result is ensured in an online manner. The algorithm has several good characteristics: (1) it omits some calculations of the distance from the present point, and therefore it is faster than all previous sensor-based algorithms; (2) it is more robust than the previous sensor-based algorithms for some self-dead-reckoning error; (3) it can generate shorter deadlock-free paths in almost all 2D worlds than the previous sensor-based algorithms.

A bstra ct- --In this paper, we propose a good pathplanning algorithm for multiple robots without mutual communication. In this research, we first select and call one ol' the multiple robots as the target robot, and then plan a collisionfree and deadlock-free path of' the targct robot toward its goal against the other moving robots in a workspace. The other robots moves as their pleases and the targct robot cannot know their future actions because of no communication. Thus we call such a workspace as an uncertain and dynamic workspace. In the workspace, the target robot obliges to find and avoid the other robots with the help of' some scnsor information. In all previous algorithms, the target robot pay attention to only avoiding its nearest robot, and consequently we could not discuss whether the target robot arrives at the goal or not (whether some deadlock occurs or not). In the proposed algorithm, not only the target robot avoids its nearest robot and also it leaves the nearest robot in order to arrive at the goal surely. Such a leave point is selected on the basis of an asymptotical decrease of the Euclidean distance bctwccn the target robot and the goal. According to this character, the robot comes close to the goal asymptotically and finally the robot arrives at the goal without occurrence of any deadlock.

Proposes a good collision-free and deadlock-free path-planning algorithm for multiple robots. The multiple robots act together in a same workspace simultaneously so as not to collide with each other and also not to be at a deadlock. Thus, some path-planning algorithms running in a known workspace where several robots move dynamically have been presented. However, they request much calculation time to select good collision-free and deadlock-free paths. The reason is as follows: The search space is generally huge because it is to be a three-dimensional quantization space including the time axis and also the path-planning algorithms select good paths by combinatorial investigation of their search space. For this point of view, the authors propose a good path-planning algorithm without generation of any collision or deadlock path in such a known and dynamic workspace. The algorithm can select a collision-free and deadlock-free path by a straight investigation of a nonquantization two-dimensional space not including the time axis without a fork, and consequently it is very efficient. The algorithm is designed based on asymptotical decrease of the Euclidean distance between the target robot and the goal. According to this property, the robot comes close to the goal asymptotically and consequently the robot arrives at the goal without occurrence of any deadlock.>

When multiple mobile robots are working in the same environment, planning of collision-free coordinated motion is necessary; here, an algorithm for planning such a motion of two mobile robots, no matter how crude the constraints of obstacles are, is proposed. The situation is modeled as a Petri net, which is considered as a useful model for describing and analyzing a system in which it is possible for some events to occur concurrently but there are constraints on the concurrence. In the Petri net, all motion constraints of robots in their paths are arranged as its firing rules, and hence collision-free coordination between the robots can be easily planning by manipulation of the firing rules. The algorithm always finds a collision-free coordinated path of two robots if there actually exists such a path in the environment. Moreover, because the algorithm does not use any knowledge of movement of the robots, precise time-varying trajectory control is not required and realization of the coordination is easy. The algorithm works efficiently even in a complex environment, indebted to the generic properties of geographical quadtree modeling for the environment. The usefulness of the algorithm is shown by several simulations.>

A motion-planning algorithm is proposed which fulfils its function fast even if shapes of the robot and its obstacles are complicated. Considering the global obstacle allocation in the robot workspace, the proposed algorithm selects intermediate positions where the mobile robot should pass from a start position to a goal position. Using a systematic motion generation method based on the closest points between the robot and its obstacles, the algorithm generated collision-free robot motions to joint the intermediate positions successively. The algorithm runs on the quadtree representation, obtained from fast conversion of a real image taken through a camera on the ceiling of the workspace. The algorithm can generate collision-free motions while following a change of obstacle allocation. In a comparison with several motion-planning algorithms, it is shown that the proposed algorithm generates fast collision-free robot motions.>

A fast algorithm is presented to measure obstacle shape in the workspace and to register the shape to the octree that is suitable for path and motion planning of the robot. The octree is constructed hierarchically by a set of cubic regions in the workspace, and its data structure is suitable for detecting interference between a moving robot and its obstacles and searching for a free region in the robot path planning.>

A fast, efficient, algorithm that processes polyhedral cones from views of an object to produce an octree representation of the object is proposed. A polyhedral cone defined by both a viewpoint and a polygonal contour of the object in the image for each view always contains the object. Thus the common region of the cones for multiple views is considered to be an approximating one of the object. The octree representation controls all cubic regions in three-dimensional space as a set of nodes with a hierarchical description in positioning, and therefore is suitable for registration of the common region. The computational complexity of the algorithm is directly proportional to the common region surface area and exponentially proportional to the finest resolution level of the octree. The calculation time of the algorithm is determined for illustrative examples of three-dimensional objects.>