Timeline for Interpolation splines of bounded curvature
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 23, 2010 at 1:19 | comment | added | j.c. | @Ganesh, Bill Thurston: I saw a talk by Nancy Lopes Garcia describing a method to find smooth_paths between two points minimizing length and further, avoiding certain subsets of the plane. Furthermore, the technique can be run dynamically with noisy inputs (if the robotic car can only see a bounded distance ahead of it and has some error in its measurements). The paper is here springerlink.com/content/w76437078g266481 though I haven't read it in detail. Apparently similar techniques were used by the Caltech team in the 2005 DARPA challenge. | |
| Sep 23, 2010 at 1:14 | comment | added | Ganesh | @Bill: Though the car can reverse and change direction, the ideal case will be to have it execute one single closed path through all the points, travelled in the forward direction. And yes, the waypoints can in general be assumed fairly sensible. I am trying to get worst case results as well to get at the limits of this approach. I'd be grateful if you respond with any insights. Thank you! | |
| Sep 23, 2010 at 0:38 | comment | added | Bill Thurston | @Ganesh: I was wondering about this kind of application, although I was imagining human-driven cars. Can the robotic cars stop and reverse direction, do you want them to always travel forward at a steady speed, or what? I'm imagining in the real application, the waypoints are actually fairly sensible, not just random points/directions. Is that right? I'll try to give a little thought to the real problem. | |
| Sep 22, 2010 at 23:45 | comment | added | Ganesh | @ Bill: I'm trying to determine paths for a car-shaped robot traversing a set of waypoints in an environment - which are the given $p_i$'s. Previous approaches, like <a href="planning.cs.uiuc.edu/node821.html"> Dubins paths </a> had discontinuous accelerations at the meeting points. Such a curve is impossible for a robotic car to navigate - therefore the second derivative requirement. Ideally, any splines (or more generally, any paths at all) I have in mind have: (a) bounded curvature (b) bounded perimeter and (c) are easy to compute, e.g. polynomial splines of small degree. | |
| Sep 22, 2010 at 3:47 | comment | added | Bill Thurston | @Ganesh: There can be many variations of this questions, with different constraints and different kinds of splines. In the Illustrator splines, one gets little splines with high curvature by making the tangent vectors short. If you constrained the degree and keep the first and 2nd derivatives bounded away from zero, then they couldn't have a small perimeter. What is your application, what are you trying to accomplish with the splines? | |
| Sep 22, 2010 at 3:21 | comment | added | Ganesh | @ Bill: If I bound the perimeter of the spline, will I still get a solution? | |
| Sep 22, 2010 at 3:13 | vote | accept | Ganesh | ||
| Sep 22, 2010 at 2:22 | history | edited | Bill Thurston | CC BY-SA 2.5 |
Replaced PDF by JPG, which should work on more browsers.
|
| Sep 22, 2010 at 1:42 | history | answered | Bill Thurston | CC BY-SA 2.5 |