On Simple Rules

The task of the week was to setup a simple car driving world and make agents drive in NetLogo. My initial setup was a closed path, four lanes forming a rectangle, where one car was moving indefinitely. My world looked like this:

netlogo1

In there, the car should travel the green path and never touch a black path. We can state simple rules to move a single car in this circuit:

  • If the path ahead of the current position is green then go forward
  • If the path ahead of the current position is not green and the path at the right of the current position is green then turn right
  • If the path ahead of the current position is not green and the path at the left of the current position is green then turn left

The rules are checked on that order, once a rule holds the next rules are not checked. And given that the car can only goes forward and never backwards, we have the minimum amount of rules to cover all the possibilities. Keep in mind that our current rules favor right turns over left turns. If we want a more partial driving without favoring one direction, we could throw a coin to decide which direction to turn.

A little more complex is the world with two lanes where a car in a given lane must keep its right:

netlogo2

If we try to use the previous rules, the inner car will not keep its right, and will invade the outer lane and follow the outer car, because it will have a green path ahead after it gets to the first corner. We need to add more rules to our set:

  • If the path ahead of the current position is green and the path at the right of the current position is green then turn right.
  • If the path ahead of the current position is green and the path at the right of the current position is not green then go forward.
  • If the path ahead of the current position is not green and the path at the right of the current position is green then turn right.
  • If the path ahead of the current position is not green and the path at the right of the current position is not green then turn left.

With these new rules the outer car still follows its right, and the inner car does not invade the outer lane. However, when the inner car gets to the first corner it gets stuck. Why? Because of our first rule and the fact that all the paths around the car are green, so for each turn it will be in the same configuration and thus it will get stuck.

To solve this problem the car should "remember" if in the last action it went forward or turned: if the car went forward then it will turn, otherwise it will forward. The new rules with memory are then:

  • If the path ahead of the current position is green and the path at the right of the current position is green and its last action was "turn right" then go forward.
  • If the path ahead of the current position is green and the path at the right of the current position is green and the last action was "go forward" then turn right.
  • If the path ahead of the current position is green and the path at the right of the current position is not green then go forward.
  • If the path ahead of the current position is not green and the path at the right of the current position is green then turn right.
  • If the path ahead of the current position is not green and the path at the right is not green then turn left.

And now both cars will keep always their right. Look how adding new lanes and agents to the world increase the number and complexity of the rules required to drive and keep the right lane, and we are simplifying lots and lots of interaction, physical and mechanical rules. This is known as complexity explosion, when the amount or rules required to simulate increases at least exponentially.

What will happen if we have a grid of lanes? Such as in the picture:

netlogo3

Our new rules with memory fails again. In this case we have to make sure the current angle of the car is set correctly. In the former cases we always assumed the car will start moving to the right of the left, but in this last example, one of them should move upwards or downwards, therefore its initial angle should be set to 90° or -90°.

For each new world, the rules should be updated, or we could try to implement general rules that work in any environment. Both ways will have their own set of problems and complexities. Currently, machine learning is a strong option to encode several rules in one model (with several layers in the case of deep learning), and could be a good approach to implement an agent in this 2D environment such as deep learning is in computer vision for self-driving cars.

On Simple Rules
Share this