📄 http:^^robios8.me.wisc.edu^~lumelsky^lumelsky.pub.html
字号:
Date: Tue, 05 Nov 1996 00:23:57 GMTServer: NCSA/1.4.1Content-type: text/html<html><head><title> Recent Projects and Selected Publication Abstracts </title><head><body><CENTER><h2> Recent Projects and Selected Publication Abstracts </h2></CENTER><UL><h3><!WA0><img src="http://robios8.me.wisc.edu/icons/redball.gif"><!WA1><A HREF="#Maze-searching">Maze-searching algorithms</A> <br><!WA2><img src="http://robios8.me.wisc.edu/icons/redball.gif"><!WA3><A HREF="#Effect_of_kinematics">Effect of kinematics in sensor-based motion planning</A> <br><!WA4><img src="http://robios8.me.wisc.edu/icons/redball.gif"><!WA5><A HREF="#Jogger_model">Dynamics and sensor-based cohntrol: the Jogger's Model</A> <br><!WA6><img src="http://robios8.me.wisc.edu/icons/redball.gif"><!WA7><A HREF="#Sensing_planning">Sensing and motion planning</A> <br><!WA8><img src="http://robios8.me.wisc.edu/icons/redball.gif"><!WA9><A HREF="#Decentralized">Decentralized intelligence: groups of robots</A> <br><!WA10><img src="http://robios8.me.wisc.edu/icons/redball.gif"><!WA11><A HREF="#Special_topics">Special topics in sensor-based motion planning: <br><ul>Tethered robots; Underwater robots; Kinematic redundancy</A></ul><!WA12><img src="http://robios8.me.wisc.edu/icons/redball.gif"><!WA13><A HREF="#Sensitive_skin">Sensitive skin project</A> <br><!WA14><img src="http://robios8.me.wisc.edu/icons/redball.gif"><!WA15><A HREF="#Human-centered">Human-centered systems</A> <br><!WA16><img src="http://robios8.me.wisc.edu/icons/redball.gif"><!WA17><A HREF="#Comp_geometry">Computational Geometry</A> <br> </h3></UL><!WA18><img alt="o" src="http://robios8.me.wisc.edu/icons/bar.gif"><a name="Maze-searching"><h2> <!WA19><img src="http://robios8.me.wisc.edu/icons/purpleball.gif">Maze-searching algorithms </h2><ul><b><li> V.J. Lumelsky, A. Stepanov, "Path Planning Strategies for aPoint Mobile Automaton Moving Amidst Unknown Obstacles of ArbitraryShape", <em> Algorithmica </em>, Springer-Verlag, 2, 403-430, 1987. </b> <p>The problem of path planning for an automaton moving in atwo-dimensional scene filled with unknown obstacles isconsidered. The automaton is presented as a point; obstaclescan be of an arbitrary shape, with continuous boundaries and offinite size; no restriction on the size of the scene isimposed. The information available to the automaton is limitedto its own current coordinates and those of the targetposition. Also, when the automaton hits an obstacle, this factis detected by the automaton's ``tactile sensor''. Thisinformation is shown to be sufficient for reaching the target orconcluding in finite time that the target cannot be reached. Aworst-case lower bound on the length of paths generated by anyalgorithm operating within the framework of the accepted modelis developed; the bound is expressed in terms of the perimetersof the obstacles met by the automaton in the scene. Algorithmsthat guarantee reaching the target (if the target is reachable),and tests for target reachability are presented. The efficiencyof the algorithms is studied, and worst-case upper bounds on thelength of generated paths are produced. <BR><BR><b><li> V.J. Lumelsky, "Algorithmic and Complexity Issues of RobotMotion in an Uncertain Environment". <em> Journal of Complexity </em>,Academic Press, 3, 146-182, 1987. </b><p>This paper presents a survey of one approach to planningcollision-free paths for an automaton operating in anenvironment with obstacles. Path planning is one of the centralproblems in robotics. Typically, the task is presented in thetwo- or three-dimensional space, with the automaton being eitheran autonomous vehicle or an arm manipulator with a fixed base.The multiplicity of approaches one finds in this area revolvesaround two basic models: in one, called <em> path planning withcomplete information</em>, perfect information about thegeometry and positions of the robot and the obstacles isassumed, whereas in the other, called <em> path planning withincomplete information</em>, an element of uncertainty about theenvironment is present. The approach surveyed here, called <em>dynamic path planning</em>, has been developed in the last fewyears; it is based on the latter model and gives rise toalgorithmic and computational issues very different from thosein the former model. The approach produces provable(non-heuristic) path planning algorithms for an automatonoperating in a highly unstructured environment where noknowledge about the obstacles is available beforehand and noconstraints on the geometry of the obstacles areimposed. <BR><BR></ul><!WA20><img alt="o" src="http://robios8.me.wisc.edu/icons/bar.gif"><a name="Effect_of_kinematics"><h2><!WA21><img src="http://robios8.me.wisc.edu/icons/purpleball.gif">Effect of kinematics in sensor-based motion planning </h2><ul><b> <li> V.J. Lumelsky, "Dynamic Path Planning for a Planar ArticulatedRobot Arm Moving Amidst Unknown Obstacles". <em> Automatica </em>,Intern. Federation of Automatic Control. Pergamon Press, Vol.23, No.5, 551-570, 1987.</b><p>This work is concerned with planning collision-freepaths for a robot arm moving in an environment filled with unknownobstacles, where any point of the robot body is subject to collision.To compensate for the uncertainty, the system is provided with sensoryfeedback information about its immediate surroundings. In such asetting, which presents significant practical and theoretical interest,human intuition is of little help, and designing algorithms with provenconvergence thus becomes an important task. We show that, given thetarget position, local feedback information is sufficient to guaranteereaching a global objective (the target position), and present anonheuristic algorithm which generates reasonable -- if, in general, notoptimal -- collision-free paths. In this approach, the path is beingplanned continuously (dynamically), based on the arm's current positionand on the sensory feedback. Here, a case of a planar arm with revolutejoints - vertical or horizontal (SCARA type) - is studied. Noconstraints on the shape of the robot links or the obstacles areimposed. The general idea is to reduce the problem of motion planningto an analysis of simple closed curves on the surface of an appropriatetwo-dimensional manifold.<BR><BR><b><li> V.J. Lumelsky, K. Sun, "A Unified Methodology forMotion Planning with Uncertainty for 2D and 3D Two-Link RobotArm Manipulators", <em> Intern. Journal of Robotics Research </em>,Vol.9, No.5, 89-104, 1990.</b><p>Most of the work on robot path planning revolves around twobasic models: the model with complete information (often calledthe Piano Mover's problem) and the model with incompleteinformation (also called path planning with uncertainty). Theapproach of dynamic path planning is based on the latter modeland produces nonheuristic (provable) algorithms for simple robotarm manipulators operating in an environment with unknownobstacles of arbitrary shapes. The algorithms assume localon-line input information coming from the arm sensors.Unfortunately, the existing techniques require that eachkinematic configuration be considered separately, which resultsin different algorithms for different kinematics. In thispaper, a unified methodology is presented for designing dynamicpath planning algorithms for two- and three-dimensional two-linkarm manipulators. The approach is independent of the specificsof the kinematic configuration, and imposes no constraints onthe shape of the arm links or obstacles in the environment. Themethodology exploits some important topological characteristicsof the configuration space. However, no explicit computation ofobstacles in the configurtation space ever takes place, whichresults in fast real-time algorithms. <BR><BR></ul><!WA22><img alt="o" src="http://robios8.me.wisc.edu/icons/bar.gif"><a name="Jogger_model"><h2> <!WA23><img src="http://robios8.me.wisc.edu/icons/purpleball.gif">Dynamics and sensor-based control: the Jogger's Model</h2><ul><b><li>V. Lumelsky, A. Shkel, ``Incorporating Body Dynamics intothe Sensor-Based Motion Planning Paradigm. The Maximum TurnStrategy''. <em>Proc. 1995 IEEE Intern. Conference onRobotics and Automation </em>, Nagoya, Japan, May 1995.</b><p>The existing approaches to sensor-based motion planning tend todeal solely with kinematic and geometric issues, and ignore thesystem dynamics. This work attempts to incorporate body dynamicsinto the paradigm of sensor-based motion planning. We considerthe case of a mass point robot operating in a planar environmentwith unknown arbitrary stationary obstacles. Given theconstraints on the robot's dynamics, sensing, and control means,conditions are formulated for generating trajectories whichguarantee convergence and the robot's safety at all times. Theapproach calls for continuous computation and is fast enough forreal time implementation. The robot plans its motion based onits velocity, control means, and sensing information about thesurrounding obstacles, and such that in case of a suddenpotential collision it can always resort to a safe emergencystopping path. Simulated examples demonstrate the algorithm'sperformance.<BR><BR><b><li> A. Shkel, V. Lumelsky, `` The Role of Time Constraintsin the Design of Control for the Jogger's Problem''. <em>Proc. IEEE Intern. Conf. on Decision and Control (CDC'95) </em>,New Orleans, 1995. </b><p>Control schemes in real-time sensor-based systems often operateunder tight time constraints determined by the system samplingrate. One area where such constraints are especially severe isthe sensor-based motion planning with dynamics inrobotics. Though very important both theoretically and inpractice, this problem has not been addressed so far. Thetypical sampling rates in such systems are 20 to 50 per second.This leaves only 20 to 50 msec for the whole cycle, includingsensing, complex geometric (intelligence) analysis, calculationsdue to dynamics and control, and motion execution. As a firstattempt to solve the problem, we show that the time constraintscan be met by a combination of a simple model with a carefullychosen analytical solution of the dynamic equations. Theresulting control scheme guarantees convergence and safety ofmotion, and blends well with kinematic path planningalgorithms. Two such strategies are discussed, one using asimple heuristic and the other with local optimization.<BR><BR></ul><!WA24><img alt="o" src="http://robios8.me.wisc.edu/icons/bar.gif"><a name="Sensing_planning"><h2> <!WA25><img src="http://robios8.me.wisc.edu/icons/purpleball.gif">Sensing and planning </h2><ul><b><li> V.J. Lumelsky, T. Skewis, "Incorporating Range Sensingin the Robot Navigation Function". <em> IEEE Trans. on Systems,Man, and Cybernetics</em>, Vol. 20, No. 5, 1058-1069, 1990.</b><p>A model of mobile robot navigation is considered whereby therobot is a point automaton operating in an environment withunknown obstacles of arbitrary shapes. The robot's inputinformation includes its own and the target point coordinates,as well as local sensing information such as from stereo visionor a range finder. We address these algorithmic issues: (i) howcan one combine sensing and planning functions thus producing<em> active sensing</em> quided by the needs of motion planning?(ii) can richer sensing (say, stereo vision as opposed totactile sensing) guarantee better performance -- say, result inshorter paths? (the general answer is ``no''). A paradigm forcombining range data with motion planning is presented. Itturns out that extensive modifications of simpler ``tactile''algorithms are needed in order to take full advantage ofadditional sensing capabilities. Two algorithms that guaranteeconvergence and exhibit different ``styles'' of behavior aredescribed and their performance is demonstrated in simulatedexamples. <BR><BR></ul><!WA26><img alt="o" src="http://robios8.me.wisc.edu/icons/bar.gif"><a name="Decentralized"><h2> <!WA27><img src="http://robios8.me.wisc.edu/icons/purpleball.gif">Decentralized intelligence: groups of robots </h2><ul><b><li> K.R. Harinarayan, V. Lumelsky, ``Sensor-Based MotionPlanning for Multiple Robots in an Uncertain Environment'', <em>Proc. IEEE Intern. Conf. on Intelligent Robots andSystems (IROS'94) </em>, 1485-1492. Munich, Germany, Sept. 1994.</b><p>This paper presents an approach to decentralized motion planning formultiple mobile robots operating in a common 2-dimensional environmentwith unknown stationary obstacles. Each robot is capable oftranslatory motion and is equipped with range sensors which allow itto sense surrounding objects. Each robot knows its current position,is able to distinguish a robot from an obstacle, and can assess theinstantaneous motion of any robot it can sense. Other than this, a robothas no knowledge about the scene, or of the paths or objectives ofother robots; there is no mutual communication among the robots. Noconstraints are imposed on the paths or shapes of robots andobstacles. Each robot plans its path toward its target dynamically,based on its current position and sensory feedback. Given theassumptions of incomplete information and decentralized planning, noprovable strategy can be designed (a simple example with a dead-lockis discussed); this naturally points to heuristic strategies. Thesuggested heuristic algorithm demonstrates a remarkable robustness andability for successful decentralized real-time motion planning in anunknown complex environment.<BR><BR></ul>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -