CS148 Assignment Path Planning

Current revision as of 18:41, 13 October 2010

Introduction

In this assignment, you will develop a ROS package for planar path planning from a robot's current location to a goal location, assuming a localized robot. Additionally, you will develop a package for playing robot soccer using your path planning package. You will evaluate your client through (graded) basic skills challenges such as navigating to specific locations and (ungraded) competition against other groups.

A video of Lisa Miller's implementation of this assignment from Spring Semester 2009.

A video of "Hefty's wicked spin" (by Nicholas and Odean) during Fall 2007 path planning match play.

Important Dates

Assigned: Friday October 1, 2010

Waypoint milestone due: Wednesday, October 13, 2010

Inter-group soccer competition: Wednesday, October 20, 2010

Project reports due: Friday, October 22, 2010 (11:59 pm)

Description

With our introduction to ROS in Assignments 1 and 2 behind us, it is now time to dig into making our robots play soccer. The next three projects will follow different approaches to autonomous robot control for 1-on-1 soccer through deliberation (this assignment), state estimation, and reaction. In the current assignment, you will use path planning algorithms to control your robot soccer player using a provided overhead localization system. In class, we will cover several different planning algorithms that you can choose from for your implementation. Your planner implementation within your control client will be providing updated game state and the static dimensions of the field. You will evaluate your client through (graded) basic skills challenges such as navigating to specific locations and (ungraded) competition against other groups.

Path Planning

For this project, your ROS implementation will deliberately plan and navigate paths for the robot. At its core, this controller must be able to maneuver the robot from its current pose on the field, expressed as the position and orientation triplet q = (x,y,\theta), to reach a desired destination, also expressed as pose q' = (x',y',\theta'). A sequence of destinations can then form a trajectory for the robot to traverse. An estimate of the current robot pose is provided by a state estimation system from robot sensing given a map of the environment through a process called localization. In this assignment, localization is performed external to the robot using overhead cameras, which could be thought of as a mini GPS. The map of the soccer field is described in the following section. This setup will allow us to focus mostly on the planning problem, whereas the next assignment deals strictly with localization from onboard robot sensing.

Given localization, a map, and a goal destination, your controller must plan and traverse a path from your current location to the goal. Planning is essentially a search over all possible routes from q to q', or configuration space. Graphs are typically used to express the space of possible poses (as graph vertices) and valid transitions between poses (as graph edges). Your robot client will need to construct graphs in the robot's configurations space and then search this graph to find good paths to traverse. For planning algorithms you have a number of options:

• Dijkstra's Algorithm
• A*
• Potential fields (Choset et al. Ch. 4)
• Wavefront planning
• Probablistic roadmaps (Kavraki et al. 1996)
• Rapidly Exploring Random Trees (Kuffner et al. 2000)

There is pseudocode available for Dijkstra's and A* search on Wikipedia as well as many other sources. There are many verisons of Dijkstra's and A* available on the internet. You are free to use these resources, but just be sure to cite anything that is not your own.

Note: even though a localization mechanism is provided, it is neither precise nor deterministic. Be careful to process state estimates with some consideration of uncertainty.

Note: path planning for this assignment is a more constrained version of [motion planning], where explicit time and pose constraints must be met.

Skills Challenges

Your grade will be determined primarily on your robot's performance in the skills challenges and reported results from challenge trials. There are two skills challenges that will be used to test the functionality of your robot controller:

• Collision-free Navigation: The navigation challenge involves driving the robot from an arbitrary starting location to a ball while avoiding objects on the floor and the field boundary. During this challenge, the robot must complete the task within 120 seconds. The outcome of a single navigation challenge trial is the time remaining at completion of the task, number of collisions, and time spent in collision.

• Goal Scoring: The goal scoring challenge requires your controller to drive your robot (starting from some arbitrary pose) to the ball (at some arbitrary position) and push the ball into the goal. During this challenge, the robot and the ball must stay in-bounds at all times and complete the task within 120 seconds. The outcome of a single scoring challenge trial is the time remaining at completion of the task, where an outcome of zero indicates time has elapsed and the robot went out of bounds.

Physical Soccer Environment

Coordinates reported by the planar_tracker system and used to report to the overhead_map system. The actual field is very roughly 4 meters long by 2.5 meters wide. In the Roomba Lab, (0,0) is the corner physically nearest the lab workstations (Pele and Pitman).

The course staff has set up the robot soccer field within the Roomba Lab for games and individual challenges associated with assignment. The field is roughly 3.8m long and 2.6m wide. The direction (θ) a robot faces is defined in radians, with θ == 0 facing in the +x direction and θ increasing as the robot turns counterclockwise. It is reasonable to assume that the theta reported from planar tracker will fall somewhere within [-2π, 2π].

Localization for these robots within the field of view is handled by a ROS publisher written by the course staff, based on the position_tracker and ar_recog packages. How to incorporate such localization information in your controller is explained in following sections. The goals are roughly 0.7m in width and slightly extend past the end boundary. A goal will consider being scored if the ball crosses the goal line.

ROS support packages

This assignment uses two experimental ROS packages from brown-ros-pkg for localizing your robot and visualizing the state of the soccer field in the Roomba Lab:

planar_tracker (brown-ros-pkg)

Localizes and publishes the pose of AR tags and color blobs on the ground plane, used by the Roomba Lab overhead localization system.

trajectory_msgs (ros.org)

ROS messages for representing trajectories for motion planning

foreign_relay (ros.org)

Shares published topics across multiple ROS masters. Topics published from remote ROS are registered with the local ROS master with the same name. "It is like a relay, except that it additionally registers its topic on a foreign master."

om_msgs (brown-ros-pkg)

ROS messages for objects to be rendered for the (optional) visualization system. (This message type is passed to web browsers connected via websockets, via the rosjs node that is running on the robot.)

rosjs (brown-ros-pkg)

A Javascript interface for ROS, used as the foundation for an (optional) visualization system.

Assignment Instructions

Your tasks for this assignment are as follows.

1. Subscribe to topics from the overhead localization system
2. Create path_planner package and write nodes for:
   • path_planner (due for October 13th Waypoint Milestone)
   • planner_navigation (due for Navigation Skills Challenge)
   • planner_goalscore (due for Goal Scoring Skills Challenge)
   • soccer_planner (due for October 20nd Soccer Competition)
3. Participate in inter-group soccer competition
4. Experiments, Reporting, and Submission

The following sections provide information to guide you through completing these tasks.

Subscribing to Overhead Localization

The current overhead localization system consists of two netbook computers that process images from two overhead mounted PS3 cameras to localize and publish objects on the robot soccer field. Each computer runs its own roscore, cmvision and ar_recog to recognize objects, and planar_tracker to localize these objects. Robots and obstacles will be recognized using AR tags, as used in the previous assignment, with unique numerical ID maintained by ar_recog. The yellow ball will be recognized using cmvision.

Localized objects are published as /tag_positions_l and /tag_positions_r topics, for each camera respectively. These topics, however, are local to roscores running on each machine. In the Roomba Lab, /tag_positions_l topic is published on the laptop "bold" and /tag_positions_r is published on "italic". It is not possible to directly subscribe to topics on "bold" and "italic" from your robot's computer, running its own roscore. Using the foreign_relay package, however, your controller will subscribe to localization topics published on remote roscores. This relay will occur transparently through foreign_relay, which creates a local version of the remote topic with the same name.

To view localization topics from your robot, first test to determine whether your computer has foreign_relay and planar_tracker installed. Try to roscd to these packages:

> roscd foreign_relay
> roscd planar_tracker

If the roscd command for foreign relay fails, this package can be installed with the following commands (assuming ROS C-Turtle distribution with Ubuntu):

> cd /opt/ros/cturtle/stacks
> svn checkout https://code.ros.org/svn/wg-ros-pkg/branches/trunk_cturtle/stacks/dance_demo/foreign_relay/
> rosmake foreign_relay

If the roscd command for planar_tracker fails, it can be installed by updating brown-ros-pkg packages

> cd /opt/ros/cturtle/stacks/brown-ros-pkg
> svn update
> rosmake planar_tracker

Assuming foreign_relay and planar_tracker are installed, you can print localization topics using rostopic using the following command in separate terminals. Run roscore in the first terminal window:

> roscore

In a second terminal window, use foreign_relay to register the remote topic (from "bold", in this case) with the local ROS master:

> rosrun foreign_relay foreign_relay.py sub /tag_positions_l http://bold:11311
registering /planar_tracker_bold_11311 @ http://bold:32785

In a third terminal window, print published localization messages from "bold" to the terminal using rostopic:

> rostopic echo tag_positions_l

Follow this process with "italic" and tag_positions_r to subscribe and view localization topics from the other camera.

Although less polished, the overhead localization technical guide has more specific information about running, calibrating, and accessing the overhead localization system as well as a technical overview.

Overhead Visualization System (Optional and Experimental)

As an alternative to rostopic, an overhead visualization system has been developed to visually display robot state in WebSockets-compatible web browsers, such as Chrome and the latest versions of Firefox and Safari. This system, overhead_map, draws state of the FC 148 field using JavaScript from published topics. The figure below shows overhead_map in use. In this figure, overhead_map is hosted by the server (right computer), rosjs and omclock are running on the "robot" (center computer), and a web browser is running on the laptop (left computer).

A temporary server for the overhead visualization has been set up to for you to visually view the state of the FC 148 pitch. From your web browser, navigate to http://10.100.0.203/overhead_map/overhead_map.html?map=soccer&address=10.100.0.115 to see a visualization of the current state (available only from the local Roomba Lab network).

Please consult the overhead_map guide for more information about how to draw objects on this canvas. More information will come about overhead drawing messages.

path_planner Package Development

The development of your path_planner package should follow this structure, and corresponds to the project milestones below:

• Create a ROS package path_planner with dependencies to rospy, std_msgs, irobot_create_2_1, planar_tracker, and trajectory_msgs. Additional dependencies for rosjs and om_msgs are needed to use the overhead visualization system. Ensure that the trajectory_msgs package is installed:

> roscd trajectory_msgs

If not installed, please add this package with the following commands:

> cd /opt/ros/cturtle/stacks
> svn checkout https://code.ros.org/svn/wg-ros-pkg/branches/arm_planning_branch/stacks/pr2_controllers/trajectory_msgs
> rosmake trajectory_msgs

• Within this package, create a node for path_planner that will subscribe to tag_positions_l and tag_position_r topics (message type Tag_Positions) and publish DOF3PlanarPath topics (message type JointTrajectory). Note: this node will need to merge and rectify information from both tag_position messages.

• Create nodes for planner_navigation and planner_goalscore that subscribe to DOF3PlanarPath topics and publish cmd_vel topics (message type Twist) for motion control of the robot in the performance of the skills challenges.

• Create a node soccer_planner that subscribes to JointTrajectory topics and publishes cmd_vel topics for motion control of the robot in the performance of playing 1-on-1 soccer.

Experiments, Reporting, and Submission

You are expected to conduct least 3 trials with 4 different initial conditions for both your planner_navigation and planner_goalscore nodes (24 trials total). For each trial, measure the properties mentioned for each challenge. All of your trials must use the same controller without modification.

Document your controller and experimental results in a written report based on the structure described in the course missive. You are welcome to experiment with additional servoing techinques and evaluate the relative performance of each. When completed, your report should be committed to the object_seeking/docs/username directory of your repository.

Project Milestones

Navigation Waypoint Milestone

Because this assignment is more involved than previous projects, an intermediate demonstration of your path planning algorithm (due October 13) is required before the overall project is completed. There will be no motion control aspect of the milestone assignment; that is, your client will not be controlling the robot. However, you do need to subscribe to overhead localization information to determine a start pose, the goal location, and obstacle positions.

For the navigation challenge, your path_planning package must generate a path from the robot's current location to the ball without colliding with obstacles. An AR tag representing a robot object will be placed on the soccer field in 404; this is your start pose and you will need to specify the id of the tag to your controller. The yellow ball will be placed on the field and the (x, y) position of the ball is your desired goal location. AR tags representing obstacles will also be placed on the field and your calculated path cannot run over the obstacles. Using this information from the overhead localization system, your controller will need to generate waypoints from the start location to the end location in the form of (x, y, \theta) for each waypoint. This path represents the path your robot will take to get to the desired goal location.

This milestone requires your package to subscribe to localization information (as /tag_positions_l and /tag_positions_r topics) and publish the computed plan (as a JointTrajectory message topic). The path computed by your path planner can be output through rostopic. Alternatively, you can visualize this plan by publishing Overhead_Map_Objs messages, which can be viewed in a web browser through rosjs.

The Milestone is due by October 13. You will need to demonstrate your Milestone implementation during class or to a TA (during their hours or by scheduling an appointment).

Skills Challenges

As stated above, your grade will be determined primarily on your robot's performance in the skills challenges and reported results from challenge trials. There are two skills challenges that will be used to test the functionality of your robot controller:

• Collision-free Navigation: The navigation challenge involves driving the robot from an arbitrary starting location to a ball while avoiding objects on the floor and the field boundary. During this challenge, the robot must complete the task within 120 seconds. The outcome of a single navigation challenge trial is the time remaining at completion of the task, number of collisions, and time spent in collision.

• Goal Scoring: The goal scoring challenge requires your controller to drive your robot (starting from some arbitrary pose) to the ball (at some arbitrary position) and push the ball into the goal. During this challenge, the robot and the ball must stay in-bounds at all times and complete the task within 120 seconds. The outcome of a single scoring challenge trial is the time remaining at completion of the task, where an outcome of zero indicates time has elapsed and the robot went out of bounds.

Inter-group Soccer Competition

Your robot will be expected to compete in an in-class robot soccer competition on October 20th. Games in this competition will consist of one 7 minute period. You will be expected to play at least 2 games in a round robin schedule. This schedule will be provided the day before the demos. Do not be late for your games as this will delay the remainder of the competition schedule. Failure to participate in the competition will result in a 10% deduction in your grade for the assignment.

At the beginning of the game after the scoring of a goal, an offensive robot begins play kicking the ball from the center of the field. The kickoff defender must start in their half until the offensive robot strikes the ball. This start could be done manually through starting or keying an event to your robot client. Afterward, no set roles are assigned to the robots. Make sure your controller can be set to defend either goal using rosparam with the cs148_team parameter.

The main play penalty is directly pushing an opposing player. When such a penalty is assessed, your robot will be taken off the field for 5 seconds and put on their 148 logo when returning. If your robot leaves the field and does not return within 3 seconds, it will be set on the "148" logo on the side of the field it is defending with a 5 second penalty assessed.

Note: Development for all groups freezes at the start of match play. Modifications to your package cannot be made during the competition, although modification to rosparams and launch files can be made. Matches will not be delayed for groups that are not ready the time schedule for their match.

Grading

Your grade for this assignment will be determined by equal weighting of your group's implementation (50%) and your individual written report (50%). The weighted breakdown of grading factors for this assignment are as follows:

Note: Demonstrations of your challenges should occur by scheduling an appointment with a TA. Soccer competitions will be held during class and the preceding hour (12-2pm).

Project Implementation

Localization 5%

Does your robot know where it is given overhead fiducial recognition?

Does your robot know where the goal, the ball, and other players are?

Goal Attainment 15%

Can your robot drive to a given location on the field?

How close to optimal is the robot's path?

How long does it take for your planner to compute?

Obstacle Avoidance 15%

Can your robot plan paths in the environment to reach a goal without traversing over obstacles?

Can your robot traverse a given path without hitting objects in the environment?

Soccer Proficiency 10%

How well does your robot player soccer in the given environment?

Controller Robustness 5%

Does your controller run without interruption or crashing?

Written Report

Introduction and Problem Statement 7%

What is your problem?

Why is it interesting?

Approach and Methods 15%

What is your approach to the problem?

How did you implement your approach and algorithms?

Could someone reproduce your algorithms?

Experiments and Results 20%

How did you validate your methods?

Describe your variables, controls, and specific tests.

Could someone reproduce your results?

Conclusion and Discussion 8%

What conclusions can be reached about your problem and approach?

What are the strengths of your approach?

What are the shortcomings of your approach?