How can one manage thousands of IF...THEN...ELSE rules?

Question

I am considering building an application, which, at its core, would consist of thousands of if...then...else statements. The purpose of the application is to be able to predict how cows move around in any landscape. They are affected by things like the sun, wind, food source, sudden events etc.

How can such an application be managed? I imagine that after a few hundred IF-statements, it would be as good as unpredictable how the program would react and debugging what lead to a certain reaction would mean that one would have to traverse the whole IF-statement tree every time.

I have read a bit about rules engines, but I do not see how they would get around this complexity.

Answer 1

The logic programming language Prolog may be what you're looking for. Your problem statement is not specific enough for me to assess if it's a good fit but it's rather similar to what you say.

A Prolog program consists of facts and rules that are applied. Here's a simple example rule that states "A cow moves to a location if the cow is hungry and there is more food in the new location than in the old location":

moves_to(Cow, Location) :-
  hungry(Cow),
  current_location(Cow, OldLoc),
  food_in(OldLoc, OldFood), food_in(Location, NewFood),
  NewFood > OldFood.

All things in capital letters are variables, things you don't know the value of. Prolog attempts to find values for these variables that satisfies all the conditions. This process is done with a powerful algorithm called unification that is the heart of Prolog and similar logic programming environments.

In addition to the rules, a database of facts is provided. A simple example that works with the rules above could be something like:

current_location(white_cow, pasture).

current_location(black_cow, barn).
hungry(black_cow).

current_location(angry_bull, forest).
hungry(angry_bull).

food_in(barn, 3).
food_in(pasture, 5).
food_in(forest, 1).

Notice that white_cow and pasture, etc. are not written in capitals. They are not variables, they are atoms.

Finally you make a query and ask what's going to happen.

?- moves_to(white_cow, Destination).
No.
?- moves_to(black_cow, Destination).
Destination = pasture
?- moves_to(Cow, Destination).
Cow = black_cow, Destination = pasture
Cow = angry_bull, Destination = barn
Cow = angry_bull, Destination = pasture

The first query asks where the white cow will move. Given the rules and the facts above, the answer is No. This can be interpreted as "I don't know" or "It doesn't move" depending on what you want.

The second query asks where the black cow moves. It moves to the pasture to eat.

The final query asks where do all the cows move. As a result you get all the possible (Cow, Destination) that make sense. In this case the black bull moves to the pasture as expected. However, the angry bull has two choices that satisfy the rules, it can either move to the pasture or the barn.

Note: It's been years since I last wrote Prolog, all examples may not be syntactically valid but the idea should be correct.

Answer 2

Tackling the if web problem you can create a rule engine where each specific rule is coded independently. A further refinement for this would be to create a domain specific language (DSL) to create the rules, however a DSL alone only displaces the problem from one code base (main) to another (DSL). Without structure the DSL will not fare any better than native language (Java, C# etc), so we'll come back to it after we find an improved structural approach.

The fundamental issue is that you are having a modelization problem. Whenever you encounter combinatorial situations like this it is a clear sign that your model abstraction that describes the situation is too coarse. You are most likely combining elements that should belong to different models in a single entity.

If you keep breaking down your model you will eventually completely dissolve this combinatorial effect. However when taking this path it is easy to get lost in your design creating an even bigger mess, perfectionism here is not necessarily your friend.

Finite state machines and rule engines are just an example of how this problem can be broken down and made more manageable. The main idea here is that a good way to rid of a combinatorial problem such as this is often to create a design and repeat it ad-nauseam in nested levels of abstraction until your system performs satisfactorily. Akin to how fractals are used to create intricate patterns. The rules remain the same no matter if you look at your system with a microscope or from a high birds eye view.

Example of applying this to your domain.

You are trying to model how cows are moving through a terrain. Though your question lacks details I would guess that your large amount of ifs include decision fragment such as if cow.isStanding then cow.canRun = true but you get bogged down as you add details of terrain for example. So for every action you want to take you have to check every aspects you can think of and repeat these verifications for the next possible action.

First we need our repeatable design, which in this case will be a FSM to model the changing states of the simulation. So the first thing I would do is implement a reference FSM, defining a state interface, a transition interface, and perhaps a transition context that can contains shared information to be made available to the other two. A basic FSM implementation will switch from one transition to another regardless of the context, this is where a rule engine comes in. The rule engine cleanly encapsulates the conditions that must be met if the transition is to take place. A rule engine here can be as simple as a list of rules each having an evaluate function returning a boolean. To check if a transition should take we place, iterate the list of rules and if any of them evaluate to false, the transition does not take place. The transition itself will contain the behavioural code to modify the current state of the FSM (and other possible tasks).

Now, if I start to implement the simulation as a single large FSM at the GOD level I end up with a LOT of possible states, transitions etc. The if-else mess looks like it's fixed but it's actually just spread around: each IF is now a rule that performs a test against a specific information of the context (which at this point pretty much contain everything) and each IF body is somewhere in the transition code.

Enter the fractals breakdown: the first step would be to create a FSM for each cow where the states are the cow's own internal states (standing, running, walking, grazing etc) and transitions between them would be affected by the environment. It's possible that the graph is not complete, for example grazing is only accessible from the standing state, any other transition is dissalowed because simply absent from the model. Here you effectively separate the data in two different models, the cow and the terrain. Each with it's own properties set. This breakdown will allow you to simplify your overall engine design. Now instead of having a single rule engine that decides all you have multiple, simpler rule engines (one for each transitions) that decide on very specific details. Many games company are using finite state machines such as this to decide on such aspects.

Because I am re-using the same code for the FSM this is basically a configuration of the FSM. Remember when we mentioned DSL's earlier? This is where the DSL can do a lot of good if you have a lot of rules & transitions to write.

Going deeper

Now GOD no longer has to deal with all the complexity on managing the cow's internal states, but we can push it further. There is still a lot of complexity involved in managing the terrain for example. This is where you decide where the breakdown is enough. If for example in your GOD you end up managing terrain dynamics (long grass, mud, dry mud, short grass etc) we can repeat the same pattern. There is nothing preventing you from embedding such logic in the terrain itself by extracting all the terrain states (long grass, short grass, muddy, dry, etc) into a new terrain FSM with transitions between the states and perhaps simple rules. For example to get to the muddy state the rule engine should check the context to find liquids, otherwise it is not possible. Now GOD got simpler still.

You can complete the system of FSM by making them autonomous and give them each a thread. This last step is not necessary but it allows you to change the system's interaction dynamically by adjusting how you delegate your decision making (launching a specialized FSM or just return a pre-determined state).

Remember how we mentioned that transitions could also do "other possible tasks"? Let's explore that by adding the possibility for different models (FSM) to communicate with each-other. You can define a set of events and allow each FSM to register listener to these events. Thus, if, for example a cow enters a terrain hex the hex can register listeners for transition changes. Here it gets a bit tricky because each FSM is implemented at very high level without any knowledge of the specific domain it harbours. However you can achieve this by having the cow publish a list of events and the cell can register if it sees events to which it can react. A good hierarchy of event family here is a good investment. Thus if the cow starts grazing the patch of terrain can record the grazing time and after some time can transition from long grass to short grass thus signalling the cow there is nothing left to eat here.

You can push deeper still by modeling the nutrient levels and growth cycle of grass, with... you guessed it... a grass FSM embedded in the terrain patch's own model.

If you push the idea far enough GOD has very little to do as all the aspects are pretty much self managed, freeing up time to spend on more godly things.

Recap

As stated above the FSM here is not the solution, just a means to illustrate that the solution to such a problem is not found in code per say but how you model your problem. There are most likely other solutions that are possible and most likely much better than my FSM proposition. However the "fractals" approach remains a good way to manage this difficulty. If done correctly you can dynamically allocate deeper levels where it matters while giving simpler models where it matters less. You can queue changes and apply them when resources become more available. In an action sequence it may not be all that important to calculate the nutrient transfer from cow to grass patch. You can however record these transitions and apply the changes at a later time or just approximate with an educated guess by simply replacing the rule engines or perhaps replacing the FSM implementation altogether with a simpler naive version for the elements that are not in the direct field of interest (that cow at the other end of the field) to allow more detailed interactions to get the focus and a larger share of resources. All this without ever revisiting the system as a whole; since each part is well isolated it becomes easier to create a drop-in replacement limiting or extending the depth of your model. By using a standard design you can build on that and maximize investments made in ad-hoc tools such as a DSL to define rules or a standard vocabulary for events, again starting at very high level and adding refinements as needed.

I would provide a code example but this is all I can afford to do right now.

Answer 3

It sounds like all these conditional statements that you're talking about should really be data that configures your program rather than part of your program itself. If you can treat them that way, then you'll be free to modify the way your program works by just changing its configuration instead of having to modify your code and recompile every time you want to improve your model.

There are a lot of different ways to model the real world, depending on the nature of your problem. Your various conditions might become rules or constraints that are applied to the simulation. Instead of having code that looks like:

if (sunLevel > 0.75) {
   foreach(cow in cows) {
       cow.desireForShade += 0.5;
   }
}
if (precipitation > 0.2) {
   foreach(cow in cows) {
       cow.desireForShelter += 0.8;
   }
}

you can instead have code that looks like:

foreach(rule in rules) {
   foreach (cow in cows) {
      cow.apply(rule);
   }
}

Or, if you can develop a linear program that models cow behavior given a number of inputs, each constraint might become a line in a system of equations. You might then turn that into a Markov model that you can iterate.

It's hard to say what the right approach is for your situation, but I think you'll have a much easier time of it if you consider your constraints to be inputs to your program and not code.

Answer 4

No one has mentioned this, so I thought I'd say it explicitly:

Thousands of "If .. Then .. Else" rules is a sign of a badly designed application.

While the domain specific data representation might look like these rules, are you absolutely certain that your implementation should resemble the domain specific representation?

Answer 5

Please, use software/computer languages that are fit for the task. Matlab is used very often to model complex systems, where you can have indeed literally thousands of conditions. Not using if/then/else clauses, but by numerical analysis. R is an open source computer language that is filled with tools and packages to do the same. But this means you also have to restate your model in more mathematical terms, so you can include both the main influences and the interactions between influences in models.

If you didn't already, please follow a course about modelling and simulation. The last thing you should do, is considering writing a model like that in terms of if - then - else. We have monte carlo markov chains, support vector machines, neural networks, latent variable analysis, ... Please don't throw yourself 100 years back by ignoring the wealth on modelling tools you have available.

Answer 6

Rules engines might help because if there are so many if/then rules it might be helpful to get them all in one place outside the program where users can edit them without needing to know a programming language. Also, visualization tools might be available.

You could also look at logic programming solutions (like Prolog). You can quickly modify the list of if/then statements and have it do things like look whether any combination of inputs would lead to certain outcomes, etc. It also might happen be cleaner in first order predicate logic than as procedural code (or than as object oriented code).

Answer 7

It's suddenly dawned on me:

You need to use a Decision Learning Tree (ID3 Algorithm).

Its highly likely that's someone has implemented it in your language. If not you could port an existing library

Answer 8

This is more of a community wiki answer, aggregating the various modelling tools suggested by other answers, I've just added additional links to resources.

I don't think there's any need to restate that you should be using a different approach to thousands of hard-coded if/else statements.

• DSL Programming (Domain Specific Language)
• Markov Model/Markov Decision process
• Rete net / Rete algorithm
• Expert System
• Matlab, (Wikipedia)
• R

Answer 9

Every large application contains thousands of if-then-else statements, not counting other flow controls, and those applications are still debugged and maintained, despite their complexity.

Also, the number of statements does not make the flow unpredictable. Asynchronous programming does. If you use deterministic algorithms synchronously, you'll have a 100% predictable behavior, every time.

You should probably explain better what are you trying to do on Stack Overflow or Code Review so that people could suggest you the precise refactoring techniques to use. You may also want to ask more precise questions, like "How do I avoid nesting too much if statements <given a piece of code>".

Answer 10

Make your application manageable by designing it well. Design your application by splitting up the various business logic into separate classes/modules. Write unit tests that test each of these classes/modules individually. This is crucial and will help you ensure that the business logic is implemented as expected.

Answer 11

There probably won't be a single way to design your way out of your problem, but you can manage the complexity of it piece by piece if you try to separate out different areas where you find yourself writing large blocks of if statements and apply solutions to each of those smaller problems.

Look to techniques like the rules talked about in Refactoring for ways to break large conditionals into manageable chunks - multiple classes with a common interface can replace a case statement, for instance.

Exit early is a big help, too. If you have error conditions, get those out of the way at the beginning of the function by throwing an exception or returning instead of letting them nest up.

If you break your conditions into predicate functions, it may be easier to keep track of them. Also, if you can get them into a standard form, it might be possible to get them in a data structure that's built dynamically, instead of a hardcoded one.

Answer 12

I would suggest you use a rules engine. In case of Java, jBPM or the Oracle BPM can be useful. Rules engines basically allow you to configure the application through XML.

Answer 13

The problem is not one well solved by "rules", whether described by "if-then" procedural code or the numerous rules solutions devised for business applications. Machine learning provides a number of mechanisms for modeling such scenarios.

Fundamentally, one has to formulate some scheme for descrete representation of the factors (e.g., sun, wind, food source, sudden events, etc) influencing the "system" (i.e., cows in a pasture). Notwithstanding the misguided belief that one can create a real valued functional representation, as opposed to discrete, no computer in the real world (including the human nervous system) is real value based or computes based on real values.

Once you have your numerical representation for the relevant factors you can construct any of several mathematical models. I would suggest a bipartite graph where one set of nodes represents cows and the other some unit area of pasture. A cow at any instance occupies some unit area of pasture. For each cow there then exists a utility value associated with the current and all other units of pasture. If the model presupposes the cow seeks to optimize (whatever such means to the cow) the utility value of its unit of pasture, then cows will move from unit to unit in effort to optimize.

A cellular automate works well for executing the model. The underlying mathematics in the real valued math world motivating cow moverment is a field gradient model. Cows move from positions of perceived lower utility value to positions of perceived higher utility value.

If one injects environmental change into the system then it will not move to a steady state solution of cow positioning. It will also become a model to which aspects of game theory could be applied; not that such would necessarily add much to this case.

The advantage here is slaughter cows or acquiring new cows can be readily managed by subtracting and adding "cow" cells to the bipartite graph, while the model is running.

Answer 14

I don't think you should define so many if-else statements. From my point of view your problem has multiple components:

• It should be async or multithreaded, because you have multiple cows with different personalities, different configuration. Each cow asks herself which direction to go in before its next move. In my opinion a sync code is a poor tool for this problem.

• The configuration of the decision tree constantly changes. It depends on the position of the actual cow, the weather, the time, the terrain, etc... Instead of building a complex if-else tree, I think we should reduce the problem to a wind rose or a direction - weight function: figure 1 - direction - weight functions for some of the rules

  The cow should always go to the direction which has the greatest sum weight. So instead of building a big decision tree you can add a set of rules (with different direction - weight functions) to each cow, and simply process the result by each time you ask the direction. You can reconfigure those rules by every position change, or by passing of the time, or you can add these details as parameters, every rule should get. It is an implementation decision. The simplest way to get a direction, to add a simple loop from 0° to 360° with 1° step. After that you can count the sum weight of each 360 direction and run through a max() function to get the proper direction.

• You don't necessarily need a neural network to do this, just one class for each rule, one class for the cows, maybe for the terrain, etc... and one class for the scenario (for example 3 cows with different rules & 1 specific terrain). figure 2 - cow app async decision nodes and connections

  • red for messaging direction - weight map through the rules
  • blue for orientation and position updates after decision making
  • green for input updates after orientation and position update
  • black for getting inputs

  note: you'll probably need a messaging framework to implement something like this

  So if making learning cows is not part of your problem, you don't need a neural network or genetic algorithms. I am not an expert of AI, but I guess if you want to adapt your cows to the real ones, then you can do it simply with a genetic algorithm and the proper set of rules. If I understand well, you need a population of cows with random rule settings. After that you can compare the behavior of real cows to the behavior of your model population and keep 10% which walk the closest path to the real ones. After that you can add new rule configuration constraints to your cow factory based on the 10% you kept, and add new random cows to the population, and so on, until you got a model cow which behaves just like the real ones...

Answer 15

I'd add that it might be the case that if you truly have thousands of IF...THEN rules you might be overspecifying. For what it's worth, neural network modeling talks I've attended often start with stating how with "a simple set of rules" they can generate fairly complex and reasonably reality-matching behavior (of, in those cases, real neurons in action). So, are you sure you need thousands of conditions? I mean, besides 4-5 aspects of weather, location of food sources, sudden events, herding, and terrain, are you really going to have many more variables? Sure, if you tried to do all possible permutations of combining those conditions, then you could easily have many thousands of rules, but that is not the right approach. Maybe a fuzzy logic style approach in which the various factors introduce a bias on each cow's location that combine to an overall decision would allow you to do this in far fewer rules.

I also agree with everyone else that the rule set should be separate from the general flow of code, so that you can easily tweak it without changing the program. You could even come up with competing rule sets and see how they do against real cow movement data. Sounds fun.

Answer 16

Expert Systems have been mentioned, which are an area of AI. To expand a little on these, reading up on Inference Engines may help you with this. A Google search might be more use - writing the DSL is the easy part, you could do this trivially with a parser like Gold Parser. The difficult part comes from building up your tree of decisions and efficiently running through them.

Many medical systems already use these engines, for example the UK's NHS Direct website.

If you're a .NET'er then Infer.NET might be useful for you.

Answer 17

Since your looking at movement of the cow, they are stuck in 360 degree direction( cows can't fly.) You also have a rate that your traveling. This can be defined as a vector.

Now how do you deal with things like the sun position, slope of the hill, loud noise?

Each of the degrees would be a variable signifying the desire to go in that direction. Say a twig snaps to the right of the cow at 90 degrees (assuming the cow faces 0 degrees). The desire to go to the right will go down and the desire to go 270 (left) will go up. Go through all the stimuli adding or subtracting their influence on the cows desire to go in a direction. Once all the stimuli is applied, the cow will go in the direction of highest desire.

You can also apply gradients so the stimuli doesn't have to be binary. For example a hill is not straight up in one direction. Maybe the cow is in a valley or on a road on a hill were its flat straight ahead, at 45* slight up hill at 90* slight down hill. At 180* steep up hill.

You can then adjust the weight of an event, and it's direction of influence. Rather then a list of if thens, you have one test looking for the max. Also when you want to add a stimuli you can just apply it before the test and you don't have to deal with adding more and more complexity.

Rather then saying the cow will go in any 360 direction lets just break it down into 36 directions. Each being 10 degrees

Rather then saying the cow will go in any 360 direction lets just break it down into 36 directions. Each being 10 degrees. Depending on how specific you need to be.

Answer 18

Use OOP. How about create a bunch of classes that handle the base conditions and run random methods to simulate what you are doing.

Get a programmer to help.

class COW_METHODS {

    Function = array('Action1','Action2',....'ActionX');

    function doAction() {
       execute(Function[random(1,5000]);
    }

    function execute(DynamicFunction) {
        exec(DynamicFunction());
    }

    Function Action1() {
        turnRight();
        eatGrass();
    }
    /*  keep adding functions for COW Methods ...  etc  */
    /*  and add classes for conditions inherit them as needed  */
    /*  keep an object to define conditions =  Singleton etc.  */
}