Creating an AI Controller - Bezier Curves and More

I've talked a bit here about my coursework for my DirectX module. I also have a project for my AI class, which I've been working on over the past few days.

The Assignment

The assignment is simple: Create a fuzzy logic controller for a racing game that will control the NPC cars. The suggested implementation is extremely simplistic - the road is represented by a line, the car by some simple symbol or sprite, and the line moving left or right represents curves.

Inputs and Outputs

The inputs to the controller are twofold. First, the position of the line relative to the car, negative being on the left, positive on the right, in pixels. Second, the relative velocity of the line with respect to the car, in pixels per second.

The output will be the suggested acceleration for the car in order to bring it closer to the line, in pixels per second per second.

Membership Functions

I've decided to use five membership functions for each input (far right, right, center, left, and far left). For output, I've decided on nine membership functions (extreme right, large right, right, slight right, center, and so on).

For the shapes and locations of these functions, I've created an HTML5 interface which allows several points for the shapes to be adjusted via sliders and text boxes. Internally, all shapes are represented as trapezoids with four points: the left base point, left peak point, right peak point, and right base point. Additionally, each trapezoid has two "curviness" settings, left and right. The idea is that with these six settings, we can create any and all of the common membership function shapes (triangle, trapezoid, curve) and any combination of them, and they are all represented identically within the code. This will allow me to tweak the membership functions easily to tune the controller.

A screenshot of the control panel for modifying the membership functions

This took a bit of doing, but I'm happy to say I've completed it and the interface is really nice.  The most difficult part was the representation of the "curviness" for the sides of the trapezoid. I wanted to keep this simple from a user standpoint, but I wasn't sure what equation to use for the curves and how to constrain the system. After some discussion with an old colleague from my chemical engineering days, Robert Coolman, I determined that a cubic spline function would be appropriate. The native capabilities of the HTML5 canvas led me to investigate the bezier curve. It turned out this was just what I needed - the bezier curve is a spline using one or two control points. Using the demo located on sitepoint.com's excelent tutorial, I was able to visualize exactly what I would use to represent the "curviness". The two control points are located on the same y coordinate as the endpoints. The x coordinate for the control points can range anywhere in between the two x coordinates, but to keep symmetry must be an equal distance from their respective end point. This distance, then, represented the "curviness". I specify some value from 0 to 10, which is then scaled to the space between the two x coordinates.

The next problem, once this was determined, was actually applying the Bezier curve's equation to find a corresponding y coordinate. This is done internally by the HTML5 canvas to draw the curve, but to use the controller I would need to be able to find it on my own. Unfortunately this would require finding the solution to a cubic equation. After some perusal of various articles including Wikipedia's Bezier Curve and Cubic Equation articles, I was able to write a function to find the real cubic root of an equation given the coefficients, and was able to determine those coefficients from the Bezier curve equation and a bit of algebra.

Rules

Given these inputs and outputs, I created a fuzzy associative map in order to ensure each situation was covered under a rule. I also plan to represent the ruleset internally in a similar fashion, to make it possible to procedurally step through the rules, and to even make it possible to tune the rules as needed.

Fuzzy Associative map covering all possible set combinations

Defuzzification

For defuzzification, I plan to keep things simple and use the Center of Maximums method. This should provide fairly accurate results as long as membership functions are mostly symmetrical - for non-symmetrical membership functions, error will be introduced due to the method not accounting for portions of the function below the maximum plateau being uneven. If I have sufficient time I may look into the center of gravity method, but for now it is beyond the scope of my plans.

The Game

The game itself will be coded using the HTML5 Canvas and JavaScript. A line will represent the centre of the road, and a sprite will represent the car. The camera will be centred on the car, but both the car and line can move freely about the game world.

There will be both a defined track (movement of the line defined using pattern movement techniques) and a user controlled track (movement of the line controlled  by the user as described in the assignment sheet).

Second AI Controller: Genetic Algorithms

The assignment also requires a second AI method to be used in addition to Fuzzy Logic. I am interested in genetic algorithms, so I plan to use a genetic algorithm to tune the fuzzy logic controller. I will then compare this result to my manually tuned controller.

Wish List

In addition to the basic features outlined above, I have several advanced features I'd like to add:

• After a track is run, the program should automatically display a summary of the performance of the AI for that course, and several useful graphs and statistics including standard deviation.
• The ability to save membership function settings to file both before and after a track is run would be useful.
• Similarly, the ability to load these membership functions from file would also be useful.
• For the genetic algorithm tuning, it would be great to watch the membership function values change in real time.
• A real-time animation of fuzzy logic operations while AI is running the track could provide insight into AI actions and assist in debugging.

Completion of some of these features could take the project beyond a simple exercise and make it a useful teaching tool for demonstrating fuzzy logic in the future.