Date of Award

2013

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Industrial and Systems Engineering and Engineering Management

Committee Chair

James J. Swain

Committee Member

Mikel D. Petty

Committee Member

Phillip A. Farrington

Committee Member

Sampson Gholston

Committee Member

Paul J. Componation

Subject(s)

Human behavior--Simulation methods, Military art and science--Simulation, Computer simulation, Virtual computer systems, Military psychology

Abstract

The automatic generation of movement routes for autonomous computer controlled entities in virtual environments is an essential and ubiquitous task in simulations of many types and applications. Practically all existing route planning algorithms, many of which are implementations of either the well-known A* algorithm or variants of it, generate routes that are optimized for some route attribute, such as length or movement time. In this research an algorithm is developed that generates routes that are not optimized but are instead realistic, where realism is defined as similarity to routes generated by humans. Before designing the realistic route planning algorithm, four new quantitative metrics of route realism based on route characteristics such as shape and length were devised. The new metrics were validated by demonstrating their ability to statistically distinguish between routes generated by humans and routes generated by the A* algorithm. Then a new version of the A* algorithm, differing from the conventional A* algorithm in that unlike A* it does not have access to complete information regarding the terrain but only to information a human in the terrain might be expected to perceive, was designed and implemented. Routes generated by the new algorithm were tested using the new realism metrics and found to be statistically indistinguishable from human generated routes. The new routes were also assessed using a Turing test and again found to be indistinguishable from human routes.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.