Transcript Ribbon Networks for Navigable Pathways of Autonomous

Ribbon Networks for Modeling
Navigable Paths of
Autonomous Agents in Virtual
Urban Environments
Peter Willemsen
School of Computing
University of Utah
Joseph Kearney
Hongling Wang
Dept. Of Computer Science
University of Iowa
IEEE VR 2003
Research Overview
 Dynamic VE
Environment
– Vehicles, pedestrians, etc…
– Lots of them!
 Behavior and scenario
programming
 Environment Modeling
Adapted to the needs of
behavior and scenario
programs
Behavior
IEEE VR 2003
Scenario
Motivation
 Virtual environments as
laboratories for
psychological study
– Child bicycle-riding behavior
 Dynamic virtual
environments need activity
– Realistic behaviors
– Replicable scenarios
 Spatial awareness
– What routes are accessible?
– Where are other objects?
– What constraints are important?
IEEE VR 2003
Focus of Talk - Environment
 Geometric Information
– Shape and curve of pathways
 Topological Information
– Interconnections between
pathways
 Logical information
– Rules governing behavior
 Occupancy Information
– Locations of objects
IEEE VR 2003
Related Research
 Farenc et al - Informed Environments
– Eurographics 1999
– Behavioral content connected to scene graph
 Donikian and Thomas - VUEMS
– Eurographics 2000, CGI 1997
– Comprehensive system for modeling urban networks of
streets, sidewalks, and tramways
 Road modeling for driving simulation
– Civil engineering design of roadways
– Desirable properties for high speed roadways
IEEE VR 2003
Ribbon Networks
 Model urban streets, sidewalks,
and navigable ways as ribbons in
space
– Curvilinear coordinate system
– Arc-length parameterized spline
– Fast lookup based on distance
 Defines geometry and orientation
of navigable surface
 Provides frame of reference for
local spatial relationships
 Annotations
(e.g. speed zones, passing regions,
features)
IEEE VR 2003
Ribbon Network Computations
 Map (X,Y,Z)
(D,O,L)
 Closest Point Computation
– Typical bottleneck
– Usual optimization techniques fail
Slow convergence and divergence
 Hybrid Method
– Combines Newton’s method and
quadratic minimization
‒ fast and robust
IEEE VR 2003
(D, O, L)
Ribbon Network Attributes
 Ribbons capable of representing (all?) types of
roadways
– Curvy, straight, engineering specified
 Cracks due to modeling errors fixed by
imperceptible numerical nudges
 Attributes annotate ribbon structure
– Lanes (parallel streams channel traffic flow)
– Speed limit signs, passing zones, and behavior
associated objects, such as flag men
 Ribbon establishes convenient local access to
attributes
IEEE VR 2003
Intersections
 Splice together incoming and
outgoing lanes
– Corridors (single lane ribbons)
 Dependencies
– Corridor relationships
– Crossing, merging, crosswalk,
right of way, traffic control
 Zero-length intersections
Change road cross-section
 Hierarchical intersections
– Pedestrians intersections
 Type and instance
IEEE VR 2003
Corridor C0
(crosses C1)
(merges_with C2)
(right_of_way C1,C2)
Paths as Overlay Ribbons
 Single-lane ribbon overlayed
on the road network
 Simplify behavior at
road/intersection junctures
– Tracking
– Collision avoidance
 Dynamically composed by
individual behaviors
 Provide egocentric, local
coordinate system for
environment queries
IEEE VR 2003
Insert picture
of Washington
and Clinton
intersection
overlaid with a
path ribbon.
Occupancy
 Spatial relationships based on ribbon structure
(INSERT PICTURE HERE)
 Occupancy queries: Two Forms
– Leader
First object on ribbon segment
– List of leaders
Ordered list of objects on ribbon segment
IEEE VR 2003
Results
 Ribbon network forms substrate for the Hank Simulator
General purpose virtual environment software
 Simulator used hundreds of hours in “production” mode
Database queries (almost) never fail
 Behavior code is greatly simplified
 Environment Description Format (EDF)
Modeling language for road networks
IEEE VR 2003
The System in Action (movie)
IEEE VR 2003
Conclusions
 Solid conceptual model of urban landscape
 Ribbon networks
– Geometry matches shape and curve of pathways
– Topology describes interconnections
– Logical attributes provide constraints and socio-cultural
aspects
– Occupancy sets up inter-object relationships
 Behaviors obtain spatial awareness
 Environment model is efficient, robust, and simple
– Supports behavior and scenario control programs
IEEE VR 2003
Future Work
 Automatic generation of models from GIS
Data
 Terrain from roads
 Incorporating pedestrian models
 Integration into physical environment
system
– VTerrain.org
IEEE VR 2003
Collaborators
• University of Iowa, Computer Science
•
•
•
•
Jim Cremer
Zhihong Wang
Scott Davis
Jill Secher
• University of Iowa, Psychology
• Jodie Plumert
• University of Iowa, Math
• Ken Atkinson
IEEE VR 2003
Acknowledgments
 Visual Database Expertise
– Joan Severson
– Shayne Gelo
– Kate Kearney
 NSF Support: CDA-96-23614, INT9724746, EIA-0130864, and IIS-0002535
IEEE VR 2003
IEEE VR 2003
IEEE VR 2003
Importance of Environment
 This slide was earlier, but didn’t like it there…
 Not sure if I like it in any case…
 Behaviors are difficult to create!
– Time consuming
 Part of Environment!
 Behaviors and enviroment mesh together
 Provide sets of queries for behavior
– Where am I? (Spatial awareness)
– Who’s near me? (Occupancy)
IEEE VR 2003
– Where can I go from here? (Geometry, topology)
Modeling Language
 System is built upon a
language
 Describes the ribbon
networks
 Example
IEEE VR 2003
Query Environment Database
 System provides run-time queries
– Where am I?
– Where can I go?
– Other examples
Overview the general query structure of the runtime system
Abstract behavioral queries
IEEE VR 2003