Module 3

2: Introduction to Distances

• Title: Euclidean and Manhattan Distances: Definition & Significance

• Content:

o Euclidean Distance:

▪ Definition: The shortest straight-line distance between two points in

Euclidean space. It's calculated using the Pythagorean theorem.

▪ Formula for 2D points (x1,y1) and (x2,y2): (x2−x1)2+(y2−y1)2

▪ Significance: Represents the actual physical distance, crucial for applications

where direct path length is paramount (e.g., measuring travel distance,
sensor range).

o Manhattan Distance (Taxicab Geometry/L1 Distance):

▪ Definition: The sum of the absolute differences of their Cartesian

coordinates. It represents the distance if movement is restricted to a grid
(like navigating city blocks).

▪ Formula for 2D points (x1,y1) and (x2,y2): ∣x2−x1∣+∣y2−y1∣

▪ Significance: Useful in grid-based environments, robotics with restricted

movement (e.g., only horizontal/vertical), pathfinding on discrete maps, and
some machine learning algorithms (e.g., k-NN for features on a grid).

Slide 3: Voronoi Graphs for Robot Path Planning

• Title: Voronoi Graphs in Robot Path Planning

• Content:

o How it's Used:

▪ Voronoi graphs partition a space into regions based on proximity to a set of

"sites" (usually obstacles or known points).

▪ In robot path planning, the Voronoi diagram's edges represent points

equidistant from two or more obstacles. These edges form a "skeleton" of
the free space.

▪ The robot can plan its path along these edges to maintain maximum
clearance from obstacles, enhancing safety and robustness.

o Advantages:

▪ Safety: Paths are inherently maximal clearance paths, reducing collision risk.
 ▪ Global Optimality (in some cases): Can find globally optimal paths in terms
of clearance.

▪ Reduced Complexity: Converts 2D/3D planning into a graph search problem.

o Disadvantages:

▪ Computational Cost: Generating Voronoi diagrams for complex

environments can be computationally intensive.

▪ Narrow Passages: Can struggle in very narrow passages where the medial
axis is ambiguous or very close to obstacles.

▪ Sensitivity to Noise: Small changes in obstacle boundaries can significantly

alter the Voronoi diagram.

o Limitations:

▪ Assumes static obstacles.

▪ Doesn't directly account for robot kinematics or dynamics.

▪ Requires accurate knowledge of the environment.

Slide 4: Key Features of Wide Path Motion Heuristics

• Title: Key Features of Wide Path Motion Heuristics

• Content:

o Definition: Heuristics designed to guide motion planning algorithms towards paths

that provide substantial clearance from obstacles, rather than just the shortest path.
The goal is often safety and robustness.

o Key Features:

▪ Prioritizes Clearance: Unlike pure shortest-path algorithms, wide path

heuristics incorporate a cost function that penalizes proximity to obstacles.

▪ Reduces Oscillation: By promoting wider paths, they can prevent the robot
from "hugging" obstacles, which can lead to jerky or unstable motion.

▪ Improved Safety Margins: Provides a buffer against localization errors,

sensor noise, or unexpected dynamic changes in the environment.

▪ Smoother Trajectories: Wider paths often translate to smoother, more

natural-looking robot movements.

▪ Examples of techniques:

▪ Using distance transforms to assign higher costs to cells near

obstacles.

▪ Integrating potential fields that repel the robot from obstacles.

 ▪ Modifying search algorithms (like A*) with a cost term related to
obstacle distance.

Slide 5: The Need for Motion Planning in Robots

• Title: Why Do Robots Need Motion Planning?

• Content:

o Autonomous Navigation: Enables robots to move from a starting point to a goal

without constant human intervention.

o Collision Avoidance: Crucial for preventing robots from damaging themselves, their
environment, or injuring humans.

o Task Execution: Many robotic tasks (e.g., pick-and-place, inspection, exploration)

require precise and safe movement.

o Efficiency and Optimality: Planning aims to find paths that are optimal in terms of
distance, time, energy consumption, or smoothness.

o Dealing with Unknowns: Allows robots to adapt to dynamic or partially unknown

environments by re-planning.

o Safety and Robustness: Ensures reliable operation in complex and often

unpredictable real-world scenarios.

o Resource Optimization: Efficient paths can conserve robot battery life and extend
operational time.

Slide 6: Lumelsky's Bug Algorithm

• Title: Lumelsky's Bug Algorithm for Path Planning

• Content:

o Concept: A simple, reactive, and robust path planning algorithm for a point robot
operating in an unknown 2D environment with static obstacles. It combines "go-to-
goal" behavior with "boundary following."

o Algorithm Steps:

1. Move-to-Goal: The robot attempts to move directly towards the target.

2. Obstacle Encounter: If an obstacle is encountered, the robot records the

point of contact (hit point).

3. Boundary Following: The robot then circumnavigates the obstacle by

following its boundary until it finds a point (leave point) that is closer to the
goal than the hit point.

4. Resumption: From the leave point, the robot resumes moving directly
towards the goal.
 o Variations (Bug 1 & Bug 2):

1. Bug 1: Circles the entire obstacle and chooses the point closest to the goal as
the leave point. Guarantees finding a path if one exists.

2. Bug 2: Leaves the obstacle boundary as soon as it re-intersects the "M-line"

(line from start to goal) and is closer to the goal than the hit point. More
efficient but might get stuck in some scenarios.

o Advantages:

1. Simple to implement.

2. Requires no prior map of the environment.

3. Guarantees finding a path if one exists (Bug 1).

o Disadvantages:

1. Paths can be very long and non-optimal.

2. Inefficient in complex environments with many obstacles.

3. Can get stuck in local minima for certain obstacle configurations (Bug 2).

Slide 7: Efficient Robot Navigation Workflow (Block Diagram)

• Title: Efficient Robot Navigation Workflow

• Content:

o [Diagram Placeholder: Describe the components for a block diagram]

o Block Diagram Description:

▪ Start/Goal Input: User defines the desired start and end points.

▪ Perception/Sensing: Robot uses sensors (Lidar, Cameras, Sonar) to gather

information about the environment (obstacles, free space).

▪ Mapping/Localization: Sensor data is used to build or update an internal

map of the environment and determine the robot's current position within
that map.

▪ Global Path Planning: Based on the map and start/goal, a high-level,

possibly optimal, path is computed (e.g., A*, RRT, PRM). This path is usually a
sequence of waypoints.

▪ Local Path Planning/Obstacle Avoidance: As the robot moves, real-time

sensor data is used to detect dynamic or previously unknown obstacles. The
global path is refined locally to avoid immediate collisions.

▪ Motion Control/Actuation: The planned path (global and local) is converted

into motor commands to move the robot's actuators (wheels, legs, arms).
 ▪ Execution & Monitoring: The robot executes the motion, constantly
monitoring its progress and the environment through sensors, feeding back
to mapping/localization and local planning.

▪ Feedback Loop: Continuous feedback ensures adaptive and robust

navigation.

Slide 8: Automatic Program Generators in Robotics

• Title: Automatic Program Generators (APG) in Robotics

• Content:

o Concept: Software tools or systems that automatically generate robot programs or

code based on high-level specifications, demonstrations, or task descriptions, rather
than requiring manual, low-level programming.

o Motivation:

▪ Reduces programming effort and time.

▪ Lowers the barrier to entry for robot programming.

▪ Minimizes human error.

▪ Enables rapid deployment and adaptation of robots to new tasks.

o Key Approaches/Methods:

▪ Programming by Demonstration (PbD): Robot learns tasks by observing

human demonstrations (e.g., kinesthetic teaching).

▪ Task-Level Programming: User specifies tasks using high-level commands,

and the APG translates them into robot-specific actions.

▪ Model-Based Programming: Uses a detailed model of the robot and

environment to generate optimal motion plans and control code.

▪ AI/Machine Learning: Learning algorithms generate optimal control policies

or program structures based on experience or simulated data.

o Examples:

▪ Code generation for industrial robot manipulators (e.g., pick-and-place

routines).

▪ Automated generation of navigation scripts for autonomous mobile robots.

▪ Systems that convert CAD models into robot machining paths.

Slide 9: Advantages and Disadvantages of Potential Field Path Planning

• Title: Potential Field Path Planning: Pros and Cons

 • Content:

o Concept: Represents the robot's environment as a field of forces. Obstacles create

repulsive forces, while the goal creates an attractive force. The robot moves by
following the gradient of the combined potential field.

o Advantages:

▪ Simplicity and Elegance: Easy to understand and implement.

▪ Real-time Response: Reactive and can handle dynamic obstacles effectively.

▪ Smooth Paths: Paths generated are typically smooth and continuous.

▪ No Explicit Map Needed (Local): Can operate with local sensor information.

▪ Scalability: Can be applied to high-dimensional configuration spaces.

o Disadvantages:

▪ Local Minima: The most significant drawback. The robot can get stuck in a
"valley" created by obstacles before reaching the goal, especially in cluttered
or U-shaped environments.

▪ Oscillation: Can lead to oscillations near obstacles or narrow passages.

▪ Deadlock: May not find a path even if one exists.

▪ Parameter Tuning: Sensitive to the tuning of attractive and repulsive force

parameters.

▪ No Global Optimality Guarantee: Does not guarantee finding the shortest or

optimal path.

Slide 10: Illustrating Potential Field Algorithm and Path Tracing

• Title: Potential Field Algorithm: Illustration & Path Tracing

• Content:

o [Diagram Placeholder: Describe a simple potential field scenario]

o Diagram Description:

▪ Imagine a 2D grid.

▪ Goal: Represented by a strong attractive force (e.g., a deep well).

▪ Obstacles: Represented by repulsive forces (e.g., hills or peaks).

▪ Robot: A small circle.

▪ Path Tracing:

1. Start the robot at an initial position.

 2. At each step, calculate the resultant force vector (sum of attractive
and repulsive forces) acting on the robot.

3. Move the robot a small step in the direction of the resultant force
vector.

4. Repeat until the robot reaches the goal or gets stuck.

▪ Illustrative Path: Draw a path starting from a random point, curving around a
circular obstacle due to the repulsive force, and then smoothly moving
towards the goal, following the "slope" of the potential field. Show how it
might get stuck in a local minimum if the obstacles form a trap.

Slide 11: Guarded Motion and Compliant Motion

• Title: Guarded Motion and Compliant Motion

• Content:

o Guarded Motion:

▪ Concept: A type of robot motion where the robot executes a planned

movement until a specific event or "guard condition" is met, at which point
the motion stops or changes.

▪ Purpose: Ensures safety and successful task completion when interaction

with the environment is expected but the exact contact point or force is
unknown.

▪ Examples:

▪ "Move down until force sensor detects contact" (e.g., placing an

object on a surface).

▪ "Move forward until proximity sensor detects obstacle" (e.g.,

approaching a workpiece).

▪ "Rotate until limit switch is pressed."

o Compliant Motion (Force Control):

▪ Concept: Robot motion where the robot actively controls the forces and
torques it exerts on its environment, allowing it to adapt to uncertainties or
irregularities in the environment.

▪ Purpose: Enables tasks requiring interaction, assembly, deburring, polishing,

or precise insertion where rigid position control would fail.

▪ Types:

▪ Active Compliance: Robot uses force/torque sensors and control

algorithms to actively adjust its position/velocity to maintain desired
forces.
 ▪ Passive Compliance: Mechanical design (e.g., Remote Center of
Compliance - RCC) allows for small, passive deflections to
accommodate misalignment.

▪ Examples:

▪ Peg-in-hole assembly (maintaining a constant insertion force).

▪ Surface following (maintaining constant contact force).

▪ Grinding or polishing (applying consistent pressure).

Slide 12: Types of Path Planning and Their Measures

• Title: Types of Path Planning and Their Measures

• Content:

o Categorization by Environment Knowledge:

▪ Global Path Planning (Offline):

▪ Description: Assumes complete and accurate knowledge of the

environment beforehand. Paths are computed entirely before
execution.

▪ Measures: Path length, computation time, path smoothness,

clearance, optimality.

▪ Local Path Planning (Online/Reactive):

▪ Description: Operates with partial or no prior knowledge of the

environment, relying heavily on real-time sensor data. Plans are
computed and adjusted continuously.

▪ Measures: Reaction time, collision avoidance rate, smoothness

(local), ability to handle dynamic obstacles.

o Categorization by Search Strategy:

▪ Sampling-Based (e.g., RRT, PRM):

▪ Description: Explores the free space by randomly sampling

configurations and connecting them to build a roadmap or tree.

▪ Measures: Probability of completeness, computation time, path

quality (smoothness, clearance), number of samples.

▪ Grid-Based (e.g., A, Dijkstra):*

▪ Description: Discretizes the environment into a grid and searches for

a path through grid cells.

▪ Measures: Path length (optimality), computation time, memory

usage, resolution dependency.
 ▪ Potential Field Based:

▪ Description: Uses artificial forces to guide the robot.

▪ Measures: Speed of convergence, ability to avoid local minima, path

smoothness.

o Categorization by Robot Model:

▪ Kinematic Planning: Considers only robot geometry and joint limits.

▪ Dynamic Planning: Accounts for robot mass, inertia, and forces/torques.

▪ Differential Constraints: Incorporates non-holonomic constraints (e.g., car-

like robots).

Slide 13: Motion Planning Terminologies

• Title: Motion Planning Terminologies with Examples

• Content:

o Obstacle:

▪ Definition: Any object or region in the environment that the robot cannot
pass through or occupy.

▪ Example: Walls, furniture, other robots, people, a box on the floor.

o Free Space (Ffree):

▪ Definition: The set of all possible configurations (positions and orientations)

of the robot where it does not collide with any obstacle.

▪ Example: For a mobile robot in a room, the free space is the area of the floor
not occupied by furniture or walls. For a robot arm, it's all joint
configurations where no link collides with itself, the base, or external
objects.

o Work Space (Task Space):

▪ Definition: The 3D physical space in which the robot operates, where its
end-effector or base moves. It's the environment perceived by humans.

▪ Example: For a robotic arm, it's the volume that its end-effector can reach.
For a mobile robot, it's the floor area it can traverse.

o Configuration Space (C-Space):

▪ Definition: An abstract space where each point uniquely represents a

complete configuration (position and orientation) of the robot. The
dimensionality of C-space equals the robot's degrees of freedom.

▪ Example:

▪ For a 2D point robot: C-space is (x, y) - 2D.

 ▪ For a 2D mobile robot with orientation: C-space is (x, y, θ) - 3D.

▪ For a robotic arm with 6 joints: C-space is (q1,q2,q3,q4,q5,q6) - 6D,

where qi are joint angles.

▪ Significance: Motion planning is often done in C-space because it simplifies

collision checking (robot becomes a point, obstacles "grow" in C-space).

Slide 14: The A Algorithm*

• Title: The A* Algorithm: Advantages, Disadvantages, and Limitations

• Content:

o Concept: A* (pronounced "A-star") is a widely used, informed search algorithm that

finds the shortest path between a start and a goal node in a graph. It combines
features of Dijkstra's algorithm and Greedy Best-First Search.

o How it Works: It maintains a priority queue of nodes to explore, prioritizing nodes

based on the sum of:

▪ g(n): The cost from the start node to node 'n'.

▪ h(n): The estimated cost (heuristic) from node 'n' to the goal.

▪ f(n) = g(n) + h(n): The total estimated cost.

o Advantages:

▪ Optimal: Guarantees finding the shortest path if the heuristic function is

admissible (never overestimates the true cost to the goal).

▪ Complete: Guarantees finding a path if one exists.

▪ Efficient: Much more efficient than uninformed search algorithms (like

Dijkstra's) due to its use of a heuristic.

▪ Widely Applicable: Used in robotics, game AI, network routing, etc.

o Disadvantages:

▪ Memory Intensive: Can consume a lot of memory, especially for large

graphs, as it needs to store all expanded nodes.

▪ Heuristic Dependent: Performance heavily relies on the quality of the

heuristic. A poor heuristic can degrade it to Dijkstra's.

▪ Not suitable for continuous spaces directly: Requires discretization of the

environment.

o Limitations:

▪ Assumes a static environment (or at least, a slowly changing one that allows
re-planning).

▪ Requires a known graph/map of the environment.

 ▪ Can be computationally expensive for very high-dimensional C-spaces or fine
grid resolutions.

Slide 15: Gross Motion Planning and Fine Motion Planning

• Title: Gross Motion Planning vs. Fine Motion Planning

• Content:

o Gross Motion Planning (Global Motion Planning):

▪ Concept: Deals with finding a high-level, collision-free path for the robot
from a start configuration to a goal configuration within the entire known
environment. It focuses on navigating large obstacles and finding a feasible
route.

▪ Scope: The entire workspace or a significant portion of it.

▪ Resolution: Often uses a coarser representation of the environment or

robot.

▪ Output: A sequence of waypoints or a general trajectory.

▪ Algorithms: A*, RRT, PRM, Dijkstra's, etc.

▪ Example: Planning the route for a mobile robot to move from one room to
another, avoiding walls and large furniture. Planning an industrial arm to
move a part from one conveyor to another.

o Fine Motion Planning (Local Motion Planning / Contact-Rich Motion Planning):

▪ Concept: Deals with precise, often contact-rich movements, typically in the

immediate vicinity of obstacles or the goal. It focuses on dealing with
uncertainties, forces, and subtle interactions.

▪ Scope: A small, localized region of the workspace, usually near a contact

event.

▪ Resolution: Requires a very high-resolution model and often involves

force/torque control.

▪ Output: Detailed trajectory, including force/torque profiles.

▪ Algorithms: Force control, impedance control, compliance control, specific

contact-aware planning algorithms.

▪ Example: Inserting a peg into a hole, grinding a surface with a specific force,
opening a door handle, assembling delicate components.

Slide 16: Advantages and Limitations of Automatic Program Generation

• Title: Automatic Program Generation (APG) in Robotics: Pros & Cons

• Content:
o Advantages:

▪ Reduced Programming Effort: Significantly cuts down on manual coding

time and complexity.

▪ Faster Deployment: Accelerates the integration and deployment of robots

for new tasks.

▪ Reduced Human Error: Automates the creation of robust and correct robot
programs, minimizing mistakes.

▪ Increased Accessibility: Lowers the barrier for non-experts to program

robots.

▪ Improved Consistency: Generates standardized and optimized code.

▪ Adaptability: Can quickly adapt to changes in environment or task

specifications.

▪ Optimality: Can generate highly optimized paths or control strategies (e.g.,

minimum time, energy).

o Limitations:

▪ Requires Accurate Models: Performance relies heavily on accurate models

of the robot, environment, and task.

▪ Generality Issues: May struggle with highly novel or unstructured tasks that
deviate significantly from learned patterns.

▪ "Black Box" Problem: Generated code can sometimes be difficult to

understand, debug, or modify manually.

▪ Computational Cost: Generation process itself can be computationally

intensive, especially for complex tasks.

▪ Data Dependency (for learning-based APG): Requires significant amounts of

data for training, which can be difficult to acquire.

▪ Safety Criticality: Ensuring the safety and reliability of automatically

generated code is a major challenge.

▪ Limited Creativity/Common Sense: APGs lack human common sense and

intuition, which can lead to suboptimal or illogical solutions in unforeseen
circumstances.