Image 01

21st Century AI

A blog about achieving meaningful Artificial Intelligence

Posts Tagged ‘Artificial Intelligence’

Creating a combat model for T. rex versus Edmontosaurus regalis.

Sunday, September 22nd, 2013

This article was originally posted at Dinosaur Island.

A T. rex is attacking an Edmontosaurus while it's companions flee (screen capture of the AI test bed program). Click to enlarge.(screen capture of the AI test bed program).

We are at the point in the development of the AI routines for the inhabitants of Dinosaur Island where it is time to make decisions about the combat models used to determine the resolution of hostile encounters. As shown in the screen capture of the Dinosaur Island AI testbed program (above), the simulation is placing the dinosaurs in various appropriate states such as: resting, eating, looking for food, looking for water, stalking prey, moving towards water, moving towards food, drinking, fighting and fleeing.

My first thought on the subject of modeling combat between T. rex and Edmontosaurus regalis, the first two resident species on the island, was that it would be handled similar to ‘melee combat’ models that I had previously used for my wargames.

Below is a page from the manual for UMS II: Nations at War explaining the 20 variable equation used to decide combat between tactical units.

The 20 variable equation used to calculate combat in our UMS II: Nations at War (c. 1992). (Scan from user's manual). Click to enlarge.

I was envisioning something similar for Dinosaur Island until I happened to see this video (below) which includes a sequence (starting at 4:45) describing hypothetical Edmontosaurus and T. rex combat.

 

What I took away from the video was:

  • Edmontosaurus regalis  is bigger than I thought. I understood the size mathematically and that they could easily grow up to 13 meters (~ 40 feet) but it wasn’t until I saw this video that it was put in to perspective, “they were as big as a railroad car.” And, “they could look into a second story window.”
  • The tail of an adult ‘bull’ Edmontosaurus regalis  was a formidable weapon.
  • T. rex, like many predators, would have preferred to attack adolescent or sick animals rather than encounter a full-size, and potentially lethal, ‘bull’.
  • The correct pronunciation is Ed-MONT-o-saur-us. I’ve been saying it wrong for the last six months!

While there is still debate about whether T. rex was a predator or a scavenger (“Tyrannosaurus rex may have been an apex predator, preying upon hadrosaurs, ceratopsians, and possibly sauropods, although some experts have suggested it was primarily a scavenger. The debate over Tyrannosaurus as apex predator or scavenger is among the longest running in paleontology.” – Wikipedia) we know of at least once case where a T. rex tooth was found in an Edmontosaurus tail that had healed from the attack (“T. rex Tooth Crown Found Embedded in an Edmontosaurus Tail – Predatory Behaviour?” “The healed bone growth indicates that the duck-billed dinosaur survived this encounter.  In February of this year, researchers from the University of Kansas and Florida reported on the discovery of evidence of a scar on fossilised skin tissue from just above the eye of an Edmontosaurus.  In a paper, published in “Cretaceous Research”, the scientists concluded that this too was evidence of an attack of a T. rex on an Edmontosaurus.”). From this we can conclude that:

  • Sometimes T. rex did attack a living Edmontosaurus.
  • Sometimes the Edmontosaurus survived the attack.

Furthermore, we know that some T. rex had suffered bone injuries during their lifetime (“An injury to the right shoulder region of Sue resulted in a damaged shoulder blade, a torn tendon in the right arm, and three broken ribs. This damage subsequently healed (though one rib healed into two separate pieces), indicating Sue survived the incident.” – Wikipedia) consistent with the type of damage that a 5 meter long tail (described as being “like a baseball bat,” in the above, video) could inflict.

In other words, combat between T. rex and Edmontosaurus regalis was not a foregone conclusion. Indeed, it was entirely possible that the Edmontosaurus could walk away unscathed while the T. rex could suffer some broken bones.

The AI for Dinosaur Island will reflect this. When deciding if the T. rex will attack the AI will have to analyze the T. rex‘s chances of victory and potential injuries (risk versus reward) considering the size of the T. rex, the age of the T. rex, the health of the T. rex, the size of the prey, the age of the prey and the health of the prey. And, when the two dinosaurs actually engage in combat the tactics employed by both will probably decide the outcome.

If the T. rex can sneak up on the Edmontosaurus until they are within 50 meters or less and then close the distance with a rush the advantage would certainly lie with the predator. If the Edmontosaurus has forewarning of the impending attack it would either attempt to flee or stand its ground and assume a defensive posture.

There is reason to believe that both Edmontosaurus and T. rex had well developed olfactory bulbs in their brains and smell was an important sense for both animals. We will add wind (and wind direction) to Dinosaur Island and incorporate this into the AI routines that control the dinosaurs. Predators will attempt to get ‘upwind’ of their prey; prey animals will ‘sniff’ the wind and respond if they smell a T. rex even if they can’t see it (see “Dinosaurs, tanks and line of sight algorithms” here).

How a dinosaur is not like a tank.

Tuesday, July 23rd, 2013

A cross-section view of the elevation that a T. Rex (named Bob) will have to traverse to get to an Edmontosaurus regalis (named Gertie). A very steep riverbank is between Bob and Gertie. Vertical axis: elevation in meters, horizontal axis: distance to goal in meters. Click to enlarge.

A cross-section view of the elevation that a T. Rex (named Bob) will have to traverse to get to an Edmontosaurus regalis (named Gertie). A very steep riverbank is between Bob and Gertie. Vertical axis: elevation in meters, horizontal axis: distance to goal in meters. Click to enlarge.

(This blog is reposted from my other site: Dinosaur-Island.com)

A few days ago I wrote about Dinosaurs, tanks and line of sight algorithms and how my previous work in modeling and simulations (M&S) for military wargames (specifically line of light algorithms) was applicable in Dinosaur Island. Today I am working on the models for dinosaur movement, speed, and what are called “least weighted path” algorithms.

You are probably familiar with least weighted path algorithms even if the term is new to you. Least weighted path algorithms are used to calculate routes in GPS units for cars or smartphones or for various internet sites like MapQuest, Google or Bing. When calculating a route there are a number of criteria to chose from. Does the user want:

  • The fastest route?
  • The shortest route?
  • The most fuel efficient route?
  • The route that avoids certain features (such as specific terrain, topography or extreme slopes)?

These options are what ‘weight’ the potential routes in a ‘least weighted’ path algorithm. For example, taking the Interstate is often the fastest route (least amount of time) but frequently is not the shortest route (least amount of distance).

Back in grad school I did my ‘comprehensive exam’ for PhD students on the subject of least weighted path algorithms. There are two very popular algorithms that solve this problem: one is Dijkstra’s algorithm (which is an exhaustive search solution) and the other is the A* algorithm, by Peter Hart, Nils Nilsson and Bertram Raphael. The primary difference between Dijkstra’s algorithm and the A* algorithm is that Dijkstra’s is guaranteed to return the optimal solution but it often takes the most time to calculate. The A* algorithm is much faster to calculate but is not guaranteed to return the optimal (or perfect) solution. In computer games we almost always use the A* algorithm because speed of calculations (especially over large maps) is more important than having the absolutely perfect route. At the bottom of this blog are links to descriptions of these algorithms and my research paper discussing an optimization of A*.

But, what does this have to do with dinosaurs and tanks?

When working on an M&S involving vehicles (like tanks) our primary concern is finding the fastest way for the tank to get from Point A to Point B. Sometimes, we want the tank to avoid entering into an area where the enemy (called OPFOR, or ‘Opposition Forces’ in military parlance) can hit it with their weapons (this is called ‘range of influence’ or ROI). This is illustrated below:

This image shows how MATE will calculate the least weighted path for a unit using roads, terrain and elevation and avoiding enemy weapons range for 'path weights'. (Click to enlarge.)

This image shows how MATE will calculate the least weighted path for a unit using roads, terrain and elevation and avoiding enemy weapons range for ‘path weights’. (Click to enlarge.)

We also want the tank to take advantage of roads and avoid swamps, rivers and ponds.The maximum speed of a tank traveling on a road is higher than the maximum speed of a tank traveling across a field. This is not the case with a T. rex or an Edmontosaurus regalis.

Another difference between tanks and dinosaurs is that as long as a tank has fuel it can go at 100% of their maximum speed (on a specific terrain) without problems. This simply isn’t the case with dinosaurs. As dinosaurs expend energy (and remember, energy is the ‘currency’ of Dinosaur Island, see: The currency of Dinosaur Island) they get tired and they can’t run as fast or as far. Also, dinosaurs run at their maximum speed only for short distances and only in extreme emergencies or at the very end of a hunt when they attack.

The illustration at the top of the blog also points out another major difference between tanks and dinosaurs: modern tanks (specifically the M1A1) has a published specification of being able to climb a 60 degree slope at a speed of 7.2 km/h (see here). That’s pretty impressive. It’s unlikely that that a T. rex could navigate a slope that steep. In the cross-section at the top of this blog we show the slopes that Bob, the T. rex, will encounter following a straight line to Gertie, the Edmontosaurus.

Clearly we’re going to need to use a least weighted path algorithm for calculating dinosaur movement so that they will avoid steep riverbanks and crevices. We also will create a table of ‘energy costs’ that dinosaurs will incur as they travel across various terrains (like swamp). These values will be used in our least weighted path algorithm.

SmallRule

Some links about least weighted path algorithms:

  • Dijkstra’s algorithm on Wikipedia has a very easy to follow description with a couple of cool animations to show how it works. Link here.

  • A* search algorithm on Wikipedia also has a couple of very nice animations to show how it works and pseudocode. Link here. By the way, I once sent Nils Nilsson an email asking him what the ‘A’ in A* stood for and he replied, “algorithm.” Now you know.

  • “An Analysis of Dimdal’s (ex-Jonsson’s) ‘An Optimal Pathfinder for Vehicles in Real-World Terrain Maps,‘ the paper for my Comprehensive Exam can be downloaded here.

Thirst or hunger? What is more important to a dinosaur?

Tuesday, July 16th, 2013

A drinking hadrosaur from a set of 1916 German collector cards "Tiere der Urwelt" (Animals of the Prehistoric World) by Heinrich Harder, from here. (Copyright expired.)

A drinking hadrosaur from a set of 1916 German collector cards “Tiere der Urwelt” (Animals of the Prehistoric World) by Heinrich Harder, from here. (Copyright expired.)

(This blog is reposted from my other site: Dinosaur-Island.com) What is more important to an animal that is very hungry and very thirsty: water or food? I just encountered this problem when writing the AI code for dinosaurs finding food and water. When ‘new’ dinosaurs are currently created in Dinosaur Island they haven’t yet eaten or drunk water so the stored values for every new animal is ’0′. Obviously, we can, and will, change that so ‘new’ dinosaurs are created with some values (these ‘new’ dinosaurs are not ‘just hatched’ dinosaurs but rather adult animals that are created and placed on Dinosaur Island for testing purposes).

Screen capture showing a very thirsty Edmontosaurus named Gertie who is now walking towards the closest observable water (click to enlarge).

Screen capture showing a very thirsty Edmontosaurus named Gertie who is now walking towards the closest observable water (click to enlarge).

The above screen capture from Dinosaur Island shows a very thirsty Edmontosaurus, named Gertie, that can see fresh water (solid blue line) in a nearby tributary. It is interesting to note that because of the height of the river bank Gertie can only see the water on the far side of the tributary. Nonetheless, Gertie is now moving towards the water she can see and will stop and drink as soon as she encounters it.

While working on the AI routines for a dinosaur finding water (see also Dinosaurs, tanks and line of sight algorithms here) I realized that some dinosaurs travel in herds and that where the herd goes is the decision of the leader. Consequently, we will need to have the ability to designate one dinosaur in a group as the leader and the others as followers. Were dinosaur herds matriarchal (led by the senior female, like elephants)? Were dinosaur herds patriarchal (like buffalo)? We just don’t know the answer to these questions but we will be able to explore the possibilities by using Dinosaur Island and observing the results.SmallRule

After posting yesterday’s blog I received an email from my friend, Siobhan, who wrote, “I think dinosaurs are closer to elephants than buffalo, and thus require a matriarch.  Please tell me who I need to pay off and how to see a matriarch implemented! (that’s me subtly casting a vote).

Bribery isn’t necessary. We believe Dinosaur Island should be flexible enough to allow the user to set up any scenario they wish. Today we added the following to the ‘Dinosaur Species’ dialog box:

The just added Herd Leadership variable (Matriarch, Patriarch or Neither in bottom right). Edmontonsosaurus, by default, is now a matriarchal herd. Screen capture (click to enlarge).

The just added Herd Leadership variable (Matriarch, Patriarch or Neither in bottom right). Edmontonsosaurus, by default, is now a matriarchal herd. Screen capture (click to enlarge).

Edmontosaurus regalis is now, by default, a matriarchal herd which means that the senior female decides where the herd goes, where it eats, where it drinks, where it rests and how to avoid predators. The default for Tyrannosaurus rex is ‘Neither’ or no herd leadership.

 

Artificial Intelligence in Modern Military Games @ GameTech 2012

Friday, March 23rd, 2012

I will be MCing the “Artificial Intelligence in Modern Military Games” panel at GameTech 2012 next week (March 29, 2012) in Orlando. I am extremely honored to be joined on this panel by:

Dr. Scott Neal Reilly is currently Principal Scientist and Vice President of the Decision Management Systems Division at Charles River Analytics, an artificial intelligence R&D company in Cambridge, MA. Dr. Neal Reilly’s research focuses on modeling emotional and social behavior in artificial agents and he was Principal Investigator for the US Army’s Culturally Aware Agents for Training Environments (CAATE) program, which focused on developing easy-to-use tools for creating interactive, intelligent, social agents.  Dr. Neal Reilly has a Ph.D. in Computer Science from Carnegie Mellon University, where he developed the Em system to model emotions in broadly capable intelligent agents. Before joining Charles River, Dr. Neal Reilly was Vice President of Production and Lead Character Builder at Zoesis Studios, which developed advanced artificial intelligence techniques for creating animated, artificially intelligent agents.

 

James Korris is CEO and President of Creative Technologies Incorporated (CTI).  CTI, named as one of Military Training Technology’s 2011 Top 100 Simulation and Training companies, is at the forefront of immersive, cognitive simulation development for government and industry.  Recent work includes one of the first DoD augmented virtuality (AV) implementations, the Call For Fire Trainer – AV, along with novel mobile applications for the Fort Sill Fires Center of Excellence.  Korris is currently leading a CTI effort supporting the SAIC Sirius team with a desktop application to mitigate analyst cognitive bias for IARPA.

From its establishment in 1999 until October 2006, Korris served as Creative Director of the U.S. Army-funded Institute for Creative Technologies at the University of Southern California.  In this pioneering “serious gaming” environment, Korris led the development of Full Spectrum Warrior, the first military application developed for the Xbox, along with desktop applications Full Spectrum Command and Full Spectrum Leader.  Korris’ team captured the DoD 2006 Modeling & Simulation award for training with Every Soldier A Sensor Simulation.  In 2007, USJFCOM recognized another Korris-led effort, the Joint Fires & Effects Trainer System as the highest-rated Close Air Support simulation trainer in the world.  In 2008, Korris was appointed to the Naval Research Advisory Committee, advising the Secretary of the Navy on its research portfolio.  Korris came to the defense industry following work in Hollywood studio production, producing and writing.  He is a member of the writers’ branch of the Academy of Television Arts and Sciences, the Writers Guild of America, the Writers Guild of Canada and the Society of Motion Picture and Television Engineers.  His work was recognized in the 2006 Smithsonian Cooper-Hewitt National Design Triennial, Saul Wurman’s eg2006 conference and as a Visionary in Bruce Mau’s Massive Change exhibition.  Korris earned a BA from Yale University and an MBA with distinction at the Harvard Business School.”

 

Dr. Michael van Lent received a PhD at the University of Michigan in 2000. His expertise is in applying cognitive science approaches to military problems. Dr. van Lent is a recognized expert in the development of advanced simulation systems for military training. He has participated in the design and development of many immersive training applications including Full Spectrum Warrior, Full Spectrum Command, the Joint Fires and Effects Trainer System (JFETS), ELECT BiLAT, UrbanSim, Helping our Heroes and the Strategic Social Interaction Modules program.

 

Robert Franceschini is a vice president and Technical Fellow at Science Applications International Corporation (SAIC). He directs the Modeling and Simulation Center of Expertise, an organization that spans SAIC’s modeling and simulation capabilities.    Prior to SAIC, Dr. Franceschini held academic and research positions at the University of Central Florida (UCF) and its Institute for Simulation and Training.  He plays an active role in science, technology, engineering, and mathematics programs in central Florida.  He received both a BS and a Ph.D. in computer science at UCF.

 

I’m looking forward to meeting you in Orlando!