02/06/08 15-494 Cognitive Robotics 1The Map Builder15-494 Cognitive RoboticsDavid S. Touretzky &Ethan Tira-ThompsonCarnegie MellonSpring 200802/06/08 15-494 Cognitive Robotics 2Horizontal Field of ViewRat: 300 deg. Human: 200 deg. AIBO: 60 deg.02/06/08 15-494 Cognitive Robotics 3Seeing A Bigger Picture●How can we assemble an accurate view of the robot's surroundings from a series of narrow camera frames?●First, convert each image to symbolic form: shapes.●Then, match the shapes in one image against the shapes in previous images.●Construct a “local map” by matching up a series of camera images.Image ShapesLocal Map02/06/08 15-494 Cognitive Robotics 4Can't Match in Camera Space●We can't match up shapes from one image to the next if the shapes are in camera coordinates. Every time the head moves, the coordinates of the shapes in the camera image change.●Solution: switch to a body-centered reference frame.●If we keep the body stationary and only move the head, the coordinates of objects won't change (much) in the body reference frame.camera plane02/06/08 15-494 Cognitive Robotics 5Planar World Assumption●How do we convert from camera-centered coordinates to body-centered coordinates?●Need to know the camera pose: can get that from the kinematics system.●Is that enough? Unfortunately, no.●Add a planar world assumption: objects lie in the plane.The robot is standing on that plane.●Now we can get object coordinates in the body frame.02/06/08 15-494 Cognitive Robotics 6Shape Spaces●camShS = camera space●groundShS = camera shapes projected to ground plane●localShS = body-centered (egocentric space);constructed by matching and importing shapesfrom groundShS across multiple images●worldShS = world space (allocentric space);constructed by matching and importing shapesfrom localShS●The robot is explicitly represented in worldShS02/06/08 15-494 Cognitive Robotics 7Invoking The Map Builder●Let's map the tic-tac-toe board:02/06/08 15-494 Cognitive Robotics 8Frame 102/06/08 15-494 Cognitive Robotics 9Frame 202/06/08 15-494 Cognitive Robotics 10Frame 302/06/08 15-494 Cognitive Robotics 11Frame 402/06/08 15-494 Cognitive Robotics 12Frame 502/06/08 15-494 Cognitive Robotics 13Final Local Map02/06/08 15-494 Cognitive Robotics 14Shape Matching Algorithm●Shape type and color must match exactly.●Coordinates must be a reasonably close match for points, blobs, and ellipses.●Lines are special, because endpoints may be invalid:–If endpoints are valid, coordinates should match.–If invalid in local map but valid in ground space, update the local map to reflect the true endpoint location.●Coordinates are updated by weighted averaging.02/06/08 15-494 Cognitive Robotics 15Noise Removal●Noise in the image can cause spurious shapes. A long line might appear as 2 short lines separated by a gap, or a noisy region might appear as a short line.●Assign a confidence value to each shape in local map.●Each time a shape is seen: increase its confidence.●If a shape should be seen but is not, decrease its confidence.●Delete shapes with negative confidence.02/06/08 15-494 Cognitive Robotics 16Where to Look?●Start with the shapes visible in the camera frame.●Move the head to fixate each shape: get a better look.●If a line runs off the edge of the camera frame, move the head to try to find the line's endpoints.–If the head can't rotate any further, give up on that endpoint.●If an object is partially cut off by the camera frame, don't add it to the map because we don't know its true shape.–Move the head to bring the object into view.02/06/08 15-494 Cognitive Robotics 17Programming the MapBuilder#include "DualCoding/DualCoding.h"class LocalMapDemo : public VisualRoutinesBehavior {public: LocalMapDemo() : VisualRoutinesBehavior() {} virtual void DoStart() { VisualRoutinesBehavior::DoStart(); MapBuilderRequest req; ... program the mapbuilder instructions mapbuilder.executeRequest(req); }};●A instance of MapBuilder is included as a member of VisualRoutinesBehavior, called mapbuilder.02/06/08 15-494 Cognitive Robotics 182 Ways To Invoke MapBuilder●If processing a single camera image, the MapBuilder returns immediately:●If multiple camera images and/or head motion required, must wait for completion (status event):mapbuilder.executeRequest(req);NEW_SHAPEVEC(blobs, BlobData, select_type<BlobData>(localShS);erouter->addListener(this, EventBase::mapbuilderEGID);mapreq_id = mapbuilder.executeRequest(req);...void processEvent (const EventBase &e) { if ( e.getGeneratorID() == EventBase::mapbuilerEGID && e.getSourceID() == mapreq_id ) { NEW_SHAPEVEC(blobs, BlobData, select_type<BlobData>(localShS)); ... }02/06/08 15-494 Cognitive Robotics 19MapBuilderRequest Parameters●RequestType–cameraMap–groundMap–localMap–worldMap●Shape parameters:–objectColors–occluderColors–maxDist–minBlobArea●Lookout control:–motionSettleTime–numSamples–sampleInterval–pursueShapes–searchArea–doScan, dTheta–manualHeadMotion02/06/08 15-494 Cognitive Robotics 20Programming the MapBuilderconst int pink_index = ProjectInterface::getColorIndex("pink");const int blue_index = ProjectInterface::getColorIndex("blue");const int orange_index = ProjectInterface::getColorIndex("orange");MapBuilderRequest req(MapBuilderRequest::localMap);req.numSamples = 5; // take mode of 5 images to filter out noisereq.maxDist = 1200; // maximum shape distance 1200 mmreq.pursueShapes = true;req.objectColors[lineDataType].insert(pink_index);req.occluderColors[lineDataType].insert(blue_index);req.occluderColors[lineDataType].insert(orange_index);req.objectColors[ellipseDataType].insert(blue_index);req.objectColors[ellipseDataType].insert(orange_index);unsigned int mapreq_id = MapBuilder::executeRequest(req);erouter->addListener(this, EventBase::mapBuilderEGID, mapreq_id, EventBase::statusETID);02/06/08 15-494 Cognitive Robotics 21Programming the MapBuilder void processEvent(const EventBase &event) { cout << “Map builder returned “ << event.getDescription() << endl; cout << “Found “ << localShS.allShapes().size() << “ shapes.” << endl; }02/06/08 15-494 Cognitive Robotics 22Qualitative Spatial Reasoning●Reading for today: How qualitative spatial reasoning can improve strategy game AIs Ken Forbus, James Mahoney, and Kevin Dill (2002)●Uses visual routinesto “reason about” maps,e.g., compute reachability,calculate paths,