Teaching Assistant: Roi Yehoshua
roiyeho@gmail.com
Agenda
• Robotic coverage problem
• Where to go next?
(C)2015 Roi Yehoshua
Robotic Coverage Problem
• Goal: Find a path for the robot(s) such that each
point in the area is visited once in minimal time
• Many applications in a many domains, such as house
cleaning, search and rescue, mapping, and
surveillance
• The general coverage problem is analogous to the
TSP problem, which is NP-complete
(C)2015 Roi Yehoshua
Grid-Based Methods
• Assume that the environment can be decomposed
into a collection of uniform grid cells
• Each cell is either occupied or free
(C)2015 Roi Yehoshua
STC Algorithm
• Spanning-tree based coverage (Gabriely & Rimon)
• Generates an optimal coverage path of the
environment, which visits every cell in the grid
exactly once
• However, it treats cells which are partially occupied
by obstacles as completely blocked
Gabriely Yoav, and Elon Rimon. "Spanning-tree based coverage of
continuous areas by a mobile robot." Annals of Mathematics and
Artificial Intelligence 31.1-4 (2001): 77-98.
(C)2015 Roi Yehoshua
STC Assumptions
• Robots with coverage tool of size D
• Uniform grid terrains, each cell of size D
• Offline coverage – grid given in advance
• Perfect localization
• Obstacles may exist, not disconnecting grid
(C)2015 Roi Yehoshua
STC
• Switch to coarse grid, each cell of size 4D
(C) Roi Yehoshua 2015
7
STC
• Define a graph G = (V, E) where:
– The vertices are the centers of all the large cells
– The edges connect adjacent unblocked large cells
• Find a spanning tree for this graph (e.g., using
DFS)
(C) Roi Yehoshua 2015
8
STC
• Robot walks along the Spanning Tree path
creating a Hamiltonian cycle over the terrain
– Keeps tree edges to one side
(C) Roi Yehoshua 2015
9
STC
D
Moving with Odometry Data
• As we have learned, you can publish Twist messages
to the /cmd_vel topic to make the robot move in the
environment
• However, calculating the exact number of
commands needed to make the robot move only
one cell in the grid can be error-prone
• Moreover, the accuracy and reliability of this process
depend on the current condition of the robot and its
internal sensors
– e.g., if the robot just started moving, the first velocity
command will take some time to take effect
(C)2015 Roi Yehoshua
Moving with Odometry Data
• Instead, we can use the odometry data to monitor
the robot's position and orientation
• Use a transform listener between the /map and
/base_footprint frames
• This way we can control more precisely the robot’s
movement
(C)2015 Roi Yehoshua
Moving with Odometry Data
void moveForwardToPosition(Position targetPosition) {
ros::Rate rate(20);
geometry_msgs::Twist moveCommand;
moveCommand.linear.x = linearSpeed;
while (ros::ok() && (abs(currPosition.first - targetPosition.first) > 10 *
linearTolerance || abs(currPosition.second - targetPosition.second) > 10 * linearTolerance))
{
cmdVelPublisher.publish(moveCommand);
rate.sleep();
getCurrentPose();
}
// Slow the speed near the target position
moveCommand.linear.x = 0.1 * linearSpeed;
while (ros::ok() && (abs(currPosition.first - targetPosition.first) > linearTolerance ||
abs(currPosition.second - targetPosition.second) > linearTolerance)) {
cmdVelPublisher.publish(moveCommand);
rate.sleep();
getCurrentPose();
}
}
(C)2015 Roi Yehoshua
Final Project
• Implement the STC algorithm using ROS + Gazebo
• More details can be found at:
http://u.cs.biu.ac.il/~yehoshr1/89-685/FinalProject/FinalProject.html
(C)2015 Roi Yehoshua
Where To Go Next?
• There are still many areas of ROS to explore:
– Integrating computer vision using OpenCV
– 3-D image processing using PCL
– Identifying your friends and family using
face_recognition
– Identifying and grasping objects on a table top
• or how about playing chess?
– Building knowledge bases with knowrob
– Learning from experience using
reinforcement_learning
(C)2015 Roi Yehoshua
Where To Go Next?
• There are now over 2000 packages and libraries
available for ROS
• Click on the Browse Software link at the top of
the ROS Wiki for a list of all ROS packages and
stacks that have been submitted for indexing.
• When you are ready, you can contribute your
own package(s) back to the ROS community
• Welcome to the future of robotics.
• Have fun and good luck!
(C)2015 Roi Yehoshua
(C)2015 Roi Yehoshua
