第四讲
Motion Planning
- Given a configuration space .
- Given start state and goal state in .
- Calculate a sequence of actions that leads from start to goal.
Convex Decomposition
Taking an arbitrarily complex concave triangle mesh and approximating it is a collection of convex objects.
Convex meshes collision checking are far more efficient than non-convex meshes.
- Convex Hull
- Not Accurate
- Exact Convex Decomposition
- NP-hard
- product a high number of clusters
- Approximate Convex Decomposition (ACD)
Probabilistic Roadmap Method (PRM)
two stage
- Map construction phase
- Randomly sample states in .
- Connect every sampled state to its neighbors
- Connect the start and goal state to the graph
- Query phase
- Run path finding algorithms like Dijkstra
How to sample uniformly in ?
- Sample uniformly over .
- Reject the sample not in the feasible area.
Challenge
- Connect neighboring points:
- requires solving dynamics (动力学的约束)
- Collision checking:
- It takes a lot of time to check if the edges are in the configuration space.
Limitations
narrow passages
Gaussian Sampling
- Generate one sample uniformly in the configuration space
- Generate another sample from a Gaussian distribution .
- If and then add .
靠边采样
Bridge Sampling
- Generate one sample uniformly in the configuration space
- Generate another sample from a Gaussian distribution .
- Define
- If and , but , add .
Rapidly-exploring Random Trees (RRT)
- Grow a tree rooted at the start state by using random samples from configuration space.
- As each sample is drawn, a connection is attempted between it and the nearest state in the tree. If the connection is in the configuration space, this results in a new state in the tree.
Challenge
- Find the nearest neighbor in the tree
- support online quick query
- KD trees.
- Need to choose a good to expand the tree efficiently.
Shortcutting
Define path:
sample two parameters .
if is true, then we replace the portion of the path between and with the straight line path.
Control System
Open Loop Control (Feedforward)
Close Loop Control (Feedback)
Error Response
- desired state
- current state
- error:
- steady-state error response:
- overshoot
- settling time
Proportional Control
差距越小，力给的越小。
Proportional-Integral Control
The more prolonged the error and the greater the amount, the larger the integral output.
- P control eliminates steady-state error only for setpoint control. (运动到固定位置)
- PI control can eliminate steady-state error for constant velocity control, but not for arbitrary trajectories. (匀速运动的控制)
Proportional-Derivative Control
- Greater control when the error is increasing. ( )
- Gentler control when the error is decreasing. ( )
can reduce overshoot.
PID Control
Putting all together.