1Qualitative Spatial Reasoningabout Sketch MapsKenneth D. Forbus Jeffrey Usher Vernell ChapmanQualitative Reasoning Group, Northwestern UniversityPresentation by Michael Hoffman•Introduction– spatial representation used in many geospatial reasoning tasks– Used to reason through a problem, not for conceptual design process– Typically drawn by hand on paperQualitative Spatial Reasoning about Sketch Maps2• Introduction– specific geospatial domain, battlespace reasoning– Warfare• Complex and important task• Requires coordinating an array of various units, equipment• Achieve goals in situations with great uncertainty and danger• Terrain effects movement, provides cover and concealment, and effects the operation of sensorsThus, geospatial reasoning must provide a role in generating and reasoning about battle plansQualitative Spatial Reasoning about Sketch Maps• Introduction– Problem with current systems• Commanders don’t want to use mouse and menus• Want to use sketch and interact with their people– Solution…nuSketch Battlespace (nSB)Qualitative Spatial Reasoning about Sketch Maps3• Overview of nSB– Avoid recognition issues by using clever interface design– Focus on richer visual and conceptual understanding of what is sketched– Two Systems have been developed:• nuSketch Battlespace (nSB): for battlespace reasoning• Sketch Knowledge Entry Associate (sKEA): general-purpose knowledge captureQualitative Spatial Reasoning about Sketch Maps– large knowledge base concerning specialized military concepts– Allows user to specify conceptual information• Types of entities• Timing information• Intent of actions–Also• Sketch terrain• Specialized areas• Paths (engagement areas, axes of advance)• Position units• Assign tasks and reasons for doing themQualitative Spatial Reasoning about Sketch Maps4• Representing Glyphs and Sketches– Basic unit in a sketch is a glyph, every glyph has ink and its content•Inkconsists of one or more polylines(points/width/color)• Content is a conceptual entity (the kind of thing that the glyph is representing)• [example] if user drew a mountain range, there would be an entity created to represent the glyph itself and an entity to represent the mountain range.Qualitative Spatial Reasoning about Sketch MapsGlyph bar -– Type of glyph content affects the interpretation of its spatial properties– [example] spatial extent representation of glyphs• Spatial extent of mountains and lakes are taken to be the spatial extent of that terrain feature.• Spatial extent of military unit is ignored, since the size of such glyphs has nothing to do with its footprint on the ground – centroid is used in spatial reasoning• Spatial extent of paths (roads and rivers) have one-dimensional extent, where width is not tied to the width of the line but is specified by special gesturesQualitative Spatial Reasoning about Sketch Maps5• Three types of Spatial Relationships– Types of Qualitative topological relationships• 2 glyphs can be disjoint (DC), touching (EC), or inside one another (TPP, NTPP)– Voronoi relationships– Diagram consisting of edges that are equidistant from a pair of points• Constructs obstacle and cost diagrams and the quad tree representation used in path-finding– Positional relationships• Provide position and orientation with respect to a global coordinate systemQualitative Spatial Reasoning about Sketch Maps• Position-finding– Two important constraints in military spatial reasoning: • fields of fire (i.e., what can someone’s weapon see?)• Observations (i.e., what can someone see?)– terrain features • Mountaints - block weapons, and thus provide cover• Forest – block visibility, and thus provide concealment…finding these positions is an important subtask in military planningQualitative Spatial Reasoning about Sketch Maps6[concealment example]• Trying to find all regions where someone could hide from us• Table indicates what kinds of terrain regions units can hide in•(V) - For each unit on our side, a new polygon is constructed by ray-casting to represent the region that is visible from that unit•(W) – polygons that result from subtracting out places where units cannot be (e.g., in lakes)•(W – V) – places where an enemy could hideQualitative Spatial Reasoning about Sketch MapsNoNoRoadYesYesCityNoNoBridgeNoNoRiverNoNoDesertPartialYesJunglePartialYesForestYesNoOpen/rolling hillsYesYesHillsYesYesMountainsCover?Concealed?Terrain Type• Fields of fire and cover, are computed similarly, using cover constraints and weapon ranges• Path-finding– Obstacles depend on type of unit moving• [example] Forests are considered untrafficablefor vehicles but trafficable by infantry– Cost of movement depends on type of terrain• [example] Takes longer for infantry to move through a swamp than through a desert– Divide space into regions• UR, “go” – unrestricted terrain• R, “slow go” – restricted terrain (high cost)• SR, “no go” – severly restricted terrain (obstacles)Qualitative Spatial Reasoning about Sketch MapsURURRoadURRCityURURBridgeSRSRRiverURURDesertRRJungleRSRForestURUROpen/rolling hillsURRHillsRSRMountainInfantryArmorTerrain Type7Example: Hypothesizing enemy intent by analogyQualitative Spatial Reasoning about Sketch MapsExample: Hypothesizing enemy intent by analogyQualitative Spatial Reasoning about Sketch Maps1. unit Bait is trying to escape Alpha Battalion which is planning to destroy it at EA killzone2. Berserker Division (hiding behind the mountain range) attacks Alpha from the rear as Alpha goes after Bait, causing considerable damage3. The ambush is successful because the attacker was concealed and could travel to an engagement area on Alpha’s path8Example: Hypothesizing enemy intent by analogyQualitative Spatial Reasoning about Sketch MapsExample: Hypothesizing enemy intent by analogyQualitative Spatial Reasoning about Sketch Maps1. Your unit, Bravo, sees enemy unit Bait trying to escape, and you are tempted to go after it2. Having heard about what happened to Alpha, you are worried.3. Using nSB, you can ask for hypothesized enemy tasks about the current situation based on the precedent sketched state9Example: Hypothesizing enemy intent by analogyQualitative Spatial Reasoning about Sketch MapsAnswer• There are 2 places that an enemy unit might be hiding, to carry out an ambush similar to what