Skip to content

Decision Making Component

Jump to bottom
Axel Böll edited this page Mar 9, 2022 · 10 revisions

Our Implementation

Finite-state machine for speed control

Dependent of the state of Traffic Lights, if the Road are free and the Target/ Speedlimit the state change to another.

  • States: Accelerate, Break, Keep_Velocity
  • In the actual implementation Yellow is handled like Red.

Finite-state machine for Maneuvers

Activate all Components needed for the states

  • States: Left-Turn, Right-Turn, Strait, Calculate new Route, (U-Turn)

Research

For Maneuvers we often see State machines like the following picture, based on this and similar pictures we think of our own state machine.

Different State Machines can work together.

Possible Decision-Making Components

Finite State Machine

Deitails

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one.

+ 
    * easy to implement 
    * can Cover a lot of scenarios 
    * clear definition of states 
    * was used by group1 last year
-
    * a lot of if/else statements 
    * many states are necessary

Markov chain

Deitails

A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. A countably infinite sequence, in which the chain moves state at discrete time steps, gives a discrete-time Markov chain. A continuous-time process is called a continuous-time Markov chain. It is named after the Russian mathematician Andrey Markov.

+ 
    * possible implementation after Finite State Machine
    * better results? 

-
    * percentages not clear
    * additional work to implement

Decision Tree

Deitails

A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm that only contains conditional control statements. Decision trees are commonly used in operations research, specifically in decision analysis, to help identify a strategy most likely to reach a goal, but are also a popular tool in machine learning.

+ 
    * easiest implementation
    * good for machine learning
-
    * more then one decision tree necessary? 
    * Can't predict based on previous state

Bayesian Model

Deitails

A Bayesian network (also known as a Bayes network, Bayes net, belief network, or decision network) is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a directed acyclic graph (DAG). Bayesian networks are ideal for taking an event that occurred and predicting the likelihood that any one of several possible known causes was the contributing factor. For example, a Bayesian network could represent the probabilistic relationships between diseases and symptoms. Given symptoms, the network can be used to compute the probabilities of the presence of various diseases.

+ 
    * good results if data quality is unclear
    
- 
    * more data needed 
    * calculation power needed

Deep learning

Deitails

Deep learning (also known as deep structured learning) is part of a broader family of machine learning methods based on artificial neural networks with representation learning. Learning can be supervised, semi-supervised or unsupervised. Deep-learning architectures such as deep neural networks, deep belief networks, deep reinforcement learning, recurrent neural networks and convolutional neural networks have been applied to fields including computer vision, speech recognition, natural language processing, machine translation, bioinformatics, drug design, medical image analysis, material inspection and board game programs, where they have produced results comparable to and in some cases surpassing human expert performance.

+
    * good results are possible
-
    * harder to implement
    * could perform badly on untrained scenarios
    * not all variables are transparent

Game Theory

Deitails

Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer science. Originally, it addressed two-person zero-sum games, in which each participant's gains or losses are exactly balanced by those of other participants.

+ 
    * predict behavior of other drivers
-
    * not feasible for our NPCs?

Conclusion

We decided to model our speed and maneuver decision making seperately because we found different approaches for each task. Generally speaking we started by implementing them as finite state machines, because we think that we dont have any data uncertainty. If our assumption prevails, we should be able to have a solid state transition model with clearly defined rules on the inputs. The first implementation of the speed state machine shows that we can have solid transitions if the input data is correct. We designed it to have the Markov Property, so we could try out reinforment learning approaches. This might be necessarry if we

Clone this wiki locally