Computational Motion Planning
Motion planning:
the use of computational methods to generate a robot’s motion to achieve a
specified task.
Copyright By PowCoder代写 加微信 powcoder
slides are from different sources, e.g. C.J. Taylor (UPenn), Uillinoise, …
http://motion.cs.illinois.edu/RoboticSystems/WhatIsMotionPlanning.html
Motion planning
• Motionplanningisacriticalcomponentofanyautonomoussystem
that exhibits intelligent behavior.
• It plays a central role in the ecosystem of components of a robot, since the
inputs to a planner include the robot’s state (coming from localization), environmental conditions (coming from perception), dynamic predictive models (coming from calibration and simulation), and task specification (coming from systems engineers and human supervisors), and the output of a motion planner is a low-level motion representation (sent to the controller).
In short, motion planning governs how all of the knowledge available to the system influences all actuation decisions.
Motion planning
The role of planning is to consume mission objectives, perception outputs, and prior information to generate a representation of the robot’s motion. The motion will be executed by the controller.
Computational Motion Planning
Graph-based Path Planning [Discrete Space]
Grassfire Algorithm
• Grassfire Algorithm is a Breadth-First-Search (BFS) algorithm and it is complete.
• It will find the shortest path (i.e., fewest number of edges) between the start and the goal if one exists.
• If no path exists that fact will be discovered.
Planning shortest paths – Dijkstra’s Algorithm
A: Start Node E: Goal Node
shortest path: A-D-C-E
Strategy: expand a cheapest node first.
Fringe is a priority queue (priority: cumulative cost)
A*Algorithm
(Informed Search)
Dijkstra’s Algorithm
(Uniform-Cost-Search)
Motion Planning in Simple Geometric Spaces
[Continuous Space]
Configuration Space (Cspace)
Introduction
• In the motion planning problems we have considered so far we have basically reduced the problem to planning on a graph where the robot can take on various discrete positions which we can enumerate and connect by edges.
• In practice, most of the robots that we build can move continuously through space.
• Configuration space is a handy mathematical and conceptual tool which was developed to help us think about these kinds of problems in a unified framework.
Configuration Space Definition:
• Theconfigurationspaceofarobotisthesetof all configurations and or positions that the robot can attain.
Configuration Space
• Let’s look at a simple example of a robot that can translate freely in the plane.
• Here we can quantify the positions that the robot can take on with a tuple (tx, ty) which denotes the coordinates of a particular reference point on the robot with respect to a fixed coordinate frame of reference.
Motion Planning in Cspace [only Translation]
Simple Robot – Translation in the Plane
• Here are a couple of configurations that this translating robot can take on along with the associated coordinates.
Simple Robot – Translation in the Plane
Simple Robot – Translation in the Plane
• In this case, we would say that our robot has two degrees of freedom and we can associate the configuration space of the robot with the points on the 2D plane – namely these (tx,ty) coordinates.
Stating the motion planning problem
v Let us assume the robot has configuration space (C-space) . A motion planning problem is specified with the following inputs:
• A kinematic and geometric description of the robot
• A geometric description of the robot’s environment
• Constraints on how the robot is allowed to move
• The robot’s start configuration
• A description of the robot’s goal (usually a configuration, a point in task- space, or a subset of configuration space)
• Optionally, an optimality criterion that should be minimized or maximized (such as minimum path length, maximum clearance from obstacles, or minimum energy expended)
v A feasible path is a continuous curve in C-space y(s):[0,1]→ that does not violate any constraints. A solution path is a feasible path beginning at the
start configuration and ending at the goal. If an optimality criterion is provided, then a solution path should also be optimal (e.g., minimize a cost function) or at least close to optimal.
Motion Constraints
There are numerous types of motion constraints that may be specified, which can be categorized by the manner in which they constrain the robot’s path:
• Local (kinematic): each point along the path must satisfy some condition, e.g., avoid collision with obstacles.
• Differential (dynamic): the derivative along the path must satisfy some condition, e.g., bounded curvature.
• Global: the entire path must satisfy some condition, e.g., path length must be within some bound.
When both kinematic and dynamic constraints are present, this is known as a kinodynamic planning problem.
Local constraints include collisions with obstacles. Differential constraints limit the derivative of the robot’s path. Global constraints are imposed on the entire path, e.g., the robot must return to its base before its battery is exhausted.
Motion Constraints
Local constraints include collisions with obstacles.
Differential constraints limit the derivative of the robot’s path.
Global constraints are imposed on the entire path, e.g., the robot must return to its base before its battery is exhausted.
In this lecture, our focus will be mainly on Local constraints.
Adding an Obstacle
Adding obstacles to the model make certain configurations in the configuration space unobtainable. This figure shows the (tx,ty) configurations that the robot CANNOT attain because of the obstacle.
• The set of configurations that the robot cannot inhabit is referred to as a CONFIGURATION SPACE OBSTACLE.
• The region of configuration space that is outside of the configuration space obstacle is termed FREE SPACE.
Configuration Space Obstacle
• On the right hand side of this figure we plot the configuration space obstacle corresponding to the geometric obstacle shown in the left half.
• Again the C-space obstacle denotes the set of configurations that the robot CANNOT attain because of collision with the obstacle.
Configuration Space Obstacle
• the dimensions and shape of the configuration space
obstacle are obtained by considering both the obstacle and the shape of the robot.
• More formally the configuration space obstacle in this case is the Minkowski sum of the obstacle.
• The Minkowski sum was named after German mathematician (1864–1909).
[1] S. M. LaValle, Planning Algorithms, : Cambridge University Press, 2006.
https://demonstrations.wolfram.com/MinkowskiSumOfConvexRobotAndObstacle/
https://demonstrations.wolfram.com/MinkowskiSumOfConvexRobotAndObstacle/
Configuration Space Obstacle
• If we have multiple obstacles in space we can visualize the union of all of the configuration space obstacles and we get a picture like this.
• Again the configuration of the robot corresponds to a point in the space and the dark areas correspond to configurations that the robot cannot attain.
Planning Path through Configuration Space
• In this setting the task of planning a path for our robot correspond to planning a trajectory through configuration space from the starting configuration to the end configuration.
Motion Planning in Cspace for Planar Arm
[only Rotation]
Two Link Planar Robot
Configuration space is a general concept can be applied to lots of robots. This slide shows a simple planar arm with two revolute joints.
Here again we can think of all of the possible configurations of this robot and associate them with a tuple of joint angles (theta_1, theta_2).
In this case the two angles can freely range from 0 to 360 degrees.
Two Link Robot + Configuration Space
Two Link Robot + Configuration Space
This movie shows our planar 2 link robot moving around along with the corresponding trajectory in configuration space.
Onceagainwecanintroduceobstaclesintothe environment and consider which configurations become infeasible because of collision.
This figure shows the robot, the obstacles and the corresponding situation in configuration space
Notethatbecauseofthewaywehavechosen coordinates for C-Space the simple polygonal obstacles actually turn into interesting looking c-space obstacles.
Configuration Space Obstacles for RR Arm
Configuration Space Obstacles for RR Arm
Planning Trajectory for 2 Link Arm
Motion Planning in Cspace [Translation + Rotation]
Translating and Rotating Robot
• Once again when we introduce obstacles into the workspace we can think about the set of configurations that are eliminated.
• In this case the configuration space has 3 dimensions and the configuration space obstacles can be thought of as 3 dimensional regions in this space.
• Note: In this case the configuration space is 3D. Watch the video for a better visualization.
• Onceagainwhenweintroduceobstaclesinto the workspace we can think about the set of configurations that are eliminated.
• In this case the configuration space has 3 dimensions and the configuration space obstacles can be thought of as 3 dimensional regions in this space.
• Except in this case the configuration space is 3D so visualization is a little more challenging.
Rotation and Translation with Obstacles
Rotation and Translation with Obstacles
Configuration Space Obstacle
Configuration Space Trajectory
Six Link Planar Robot
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com