Computational Motion Planning
slides are from different sources, e.g. C.J. Taylor (UPenn), …
Introduction to The Motion Planning Problem
Copyright By PowCoder代写 加微信 powcoder
• A special case of the more general AI planning problem
• The goal is to develop techniques that would allow a robot or robots to automatically decide how to move from one position or configuration to another.
• E.g.: laundry robot, ideally we want the robot to come up with all the required sequence of actions and perform them by its own; from finding the laundry, taking it downstairs, putting it in the washing machine, taking it out, folding it, ….
• Specifically concerned with planning motions – get robot from place A to B
• In many cases this becomes a geometry problem, where the goal is to guide the robot through a particular trajectory that avoids all the obstacles that we know about in the environment.
Motion Planning for Robotics
• Can be applied to a wide variety of robotic systems.
Quadrotor/Drone
An Example – the PacMan problem
• How does the computer guide the ghosts back to their lair when they are eaten from wherever it was?
Planning on a grid
A simple depiction of the PacMan problem:
• In this example the robot can move between adjacent cells on the grid.
• The dark squares indicate obstacles that the robot cannot traverse.
• The goal is to move from the START cell to the END cell.
Graph Structure
• We can think of the unoccupied cells as nodes and draw edges between adjacent cells as shown here.
• This set of nodes and edges constitutes a mathematical structure known as a graph.
Graph Structure
A graph, G, consists of a set of vertices, V, and a set of Edges, E, that link pairs of vertices.
The edges are often annotated with numerical values to indicate relevant quantities like distances or costs.
Graph are mathematical concepts that are very helpful in modeling a variety of complex maps in the world.
Examples of Graphs in the Wild- Transit Map
Nodes: stations
Edges: railing between stations
Examples of Graphs in the Wild – Toll Chart
Pittsburgh
Philadelphia
Nodes: cities
Edges: toll road between cities
Goal: find a path with minimum cost
Washington
Examples of Graphs in the Wild – World Wide Web
Nodes: webpages
Edges: link between webpages
Graph Structure
• In this grid graph we will implicitly associate a cost or distance of 1 with every edge in the graph since they link adjacent cells.
Planning on a grid
• The goal is to construct a path through the grid/ graph from the start to the goal.
Planning on a grid
• Typically there are many possible paths between two nodes.
• We are usually interested in the shortest paths.
Planning on a grid
o Construct the shortest path between the start and the goal location.
• Graph-based Planning:
• There are several techniques to find the shortest path.
• Grassfire/ Breadth First Search algorithm
• Dijkstra’s algorithm
• A* algorithm
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com