如何在Java中实现FSM - 有限状态机

Question

我有工作要做,我需要你的帮助.我们想要实现一个FSM - Finite State Machine,以识别char序列(如:A,B,C,A,C),并告诉它是否被接受.

我们认为,实行三类:State,Event和Machine.该state班提出的一个节点FSM,我们认为有实现它State design pattern,每个节点将抽象类扩展状态和每一个类可以处理不同类型的事件,并指示过渡到一个新的状态.你认为这是个好主意吗？

第二件事,我们不知道如何保存所有过渡.我们再一次考虑用某种方式来实现它,它具有map起点并且在下一个状态下获得某种向量,但我不确定这是一个好主意.

我很乐意得到一些如何实现它的想法,或者你可以给我一些起点.

我应该如何保存FSM,这意味着我应该如何在程序开始时构建树？我用Google搜索并找到了很多例子但没有任何帮助我的东西.

非常感谢.

Answer 1

状态机的核心是转换表,它将状态和符号(您正在调用的事件)转换为新状态.这只是一个双索引的状态数组.为了理智和类型安全,将状态和符号声明为枚举.我总是以某种方式添加"长度"成员(特定于语言)来检查数组边界.当我手工编写FSM时,我用行空格式格式化行和列格式的代码.状态机的其他元素是初始状态和接受状态集.接受状态集的最直接实现是由各州索引的一系列布尔值.但是,在Java中,枚举是类,您可以指定参数"接受"

对于机器类型,您可以将其编写为泛型类.它需要两个类型参数,一个用于状态,一个用于符号,一个用于转换表的数组参数,一个用于初始化的状态.唯一的其他细节(虽然它很关键)是你必须调用Enum.ordinal()来获得一个适合索引转换数组的整数,因为你没有直接声明带有枚举索引的数组的语法(尽管应该是).

要抢占一个问题,EnumMap将不适用于转换表,因为所需的密钥是一对枚举值,而不是一个枚举值.

enum State {
    Initial( false ),
    Final( true ),
    Error( false );
    static public final Integer length = 1 + Error.ordinal();

    final boolean accepting;

    State( boolean accepting ) {
        this.accepting = accepting;
    }
}

enum Symbol {
    A, B, C;
    static public final Integer length = 1 + C.ordinal();
}

State transition[][] = {
    //  A               B               C
    {
        State.Initial,  State.Final,    State.Error
    }, {
        State.Final,    State.Initial,  State.Error
    }
};

Answer 2

EasyFSM是一个动态Java库,可用于实现FSM.

您可以在以下位置找到相同的文档: Java中的有限状态机

此外,您可以从以下位置下载该库: Java FSM Library:DynamicEasyFSM

Answer 3

嗯,我建议您使用Flyweight来实现状态.目的:避免大量小对象的内存开销.状态机可以变得非常非常大.

http://en.wikipedia.org/wiki/Flyweight_pattern

我不确定是否需要使用设计模式State来实现节点.状态机中的节点是无状态的.它们只是将当前输入符号与当前状态的可用转换相匹配.也就是说,除非我完全忘记它们是如何工作的(这是明确的可能性).

如果我正在编码,我会做这样的事情:

interface FsmNode {
  public boolean canConsume(Symbol sym);
  public FsmNode consume(Symbol sym);
  // Other methods here to identify the state we are in
}

  List<Symbol> input = getSymbols();
  FsmNode current = getStartState();
  for (final Symbol sym : input) {
    if (!current.canConsume(sym)) {
      throw new RuntimeException("FSM node " + current + " can't consume symbol " + sym);
    }
    current = current.consume(sym);
  }
  System.out.println("FSM consumed all input, end state is " + current);

Flyweight在这种情况下会做什么？好吧,在FsmNode下面可能有这样的东西:

Map<Integer, Map<Symbol, Integer>> fsm; // A state is an Integer, the transitions are from symbol to state number
FsmState makeState(int stateNum) {
  return new FsmState() {
    public FsmState consume(final Symbol sym) {
      final Map<Symbol, Integer> transitions = fsm.get(stateNum);
      if (transisions == null) {
        throw new RuntimeException("Illegal state number " + stateNum);
      }
      final Integer nextState = transitions.get(sym);  // May be null if no transition
      return nextState;
    }
    public boolean canConsume(final Symbol sym) {
      return consume(sym) != null;
    }
  }
}

这会在需要使用的基础上创建State对象,它允许您使用更有效的底层机制来存储实际的状态机.我在这里使用的那个(Map(整数,地图(符号,整数)))并不特别有效.

请注意,Wikipedia页面侧重于许多有些类似的对象共享相似数据的情况,就像Java中的String实现中的情况一样.在我看来,Flyweight更为通用,涵盖任何按需创建具有短寿命的对象(使用更多的CPU来节省更高效的底层数据结构).

Answer 4

考虑简单,轻量级的Java库EasyFlow.从他们的文档:

使用EasyFlow,您可以:

• 实现复杂的逻辑,但保持您的代码简单和干净
• 轻松优雅地处理异步调用
• 通过使用事件驱动的编程方法来避免并发
• 通过避免递归来避免StackOverflow错误
• 简化复杂Java应用程序的设计,编程和测试

Answer 5

您可以通过两种不同的方式实现有限状态机.

选项1:

具有预定义工作流程的有限状态机:如果您事先知道所有状态并且状态机几乎是固定的,则建议您在将来不做任何更改

1. 确定应用程序中的所有可能状态

2. 识别应用程序中的所有事件

3. 确定应用程序中的所有条件,这可能导致状态转换

4. 事件的发生可能导致状态转换

5. 通过决定状态和转换的工作流来构建有限状态机.

   例如,如果事件1发生在状态1,则状态将被更新,并且机器状态可能仍处于状态1.

   如果事件2发生在状态1,则在某些条件评估中,系统将从状态1移动到状态2

此设计基于状态和上下文模式.

看看有限状态机原型类.

选项2:

行为树: 如果状态机工作流程经常更改,则建议使用.您可以在不破坏树的情况下动态添加新行为.

基本Task类为所有这些任务提供了一个接口,leaf任务是刚刚提到的任务,而父任务是决定下一个要执行的任务的内部节点.

该任务只有他们需要实际做的是要求他们的逻辑,一个任务是否已经开始所有的决策逻辑与否,是否需要更新,如果它已经成功完成了,等在被分组TaskController类,并由组合添加.

该装饰是通过包装它,并给它附加的逻辑来"装饰"另一个类的任务.

最后,Blackboard类是父AI所拥有的类,每个任务都有引用.它作为所有叶子任务的知识数据库

看看这个文章通过海梅Barrachina Verdia了解更多详情

Answer 6

我用java设计并实现了一个简单的有限状态机示例。

IFiniteStateMachine：管理有限状态机的公共接口，
例如向有限状态机添加新状态或通过
特定操作转换到下一个状态。

interface IFiniteStateMachine {
    void setStartState(IState startState);

    void setEndState(IState endState);

    void addState(IState startState, IState newState, Action action);

    void removeState(String targetStateDesc);

    IState getCurrentState();

    IState getStartState();

    IState getEndState();

    void transit(Action action);
}

IState：获取状态相关信息的公共接口，
例如状态名称和连接状态的映射。

interface IState {
    // Returns the mapping for which one action will lead to another state
    Map<String, IState> getAdjacentStates();

    String getStateDesc();

    void addTransit(Action action, IState nextState);

    void removeTransit(String targetStateDesc);
}

Action：将导致状态转换的类。

public class Action {
    private String mActionName;

    public Action(String actionName) {
        mActionName = actionName;
    }

    String getActionName() {
        return mActionName;
    }

    @Override
    public String toString() {
        return mActionName;
    }

}

StateImpl：IState 的实现。我应用了HashMap等数据结构来保存操作-状态映射。

public class StateImpl implements IState {
    private HashMap<String, IState> mMapping = new HashMap<>();
    private String mStateName;

    public StateImpl(String stateName) {
        mStateName = stateName;
    }

    @Override
    public Map<String, IState> getAdjacentStates() {
        return mMapping;
    }

    @Override
    public String getStateDesc() {
        return mStateName;
    }

    @Override
    public void addTransit(Action action, IState state) {
        mMapping.put(action.toString(), state);
    }

    @Override
    public void removeTransit(String targetStateDesc) {
        // get action which directs to target state
        String targetAction = null;
        for (Map.Entry<String, IState> entry : mMapping.entrySet()) {
            IState state = entry.getValue();
            if (state.getStateDesc().equals(targetStateDesc)) {
                targetAction = entry.getKey();
            }
        }
        mMapping.remove(targetAction);
    }

}

FiniteStateMachineImpl：IFiniteStateMachine 的实现。我使用 ArrayList 来保存所有状态。

public class FiniteStateMachineImpl implements IFiniteStateMachine {
    private IState mStartState;
    private IState mEndState;
    private IState mCurrentState;
    private ArrayList<IState> mAllStates = new ArrayList<>();
    private HashMap<String, ArrayList<IState>> mMapForAllStates = new HashMap<>();

    public FiniteStateMachineImpl(){}
    @Override
    public void setStartState(IState startState) {
        mStartState = startState;
        mCurrentState = startState;
        mAllStates.add(startState);
        // todo: might have some value
        mMapForAllStates.put(startState.getStateDesc(), new ArrayList<IState>());
    }

    @Override
    public void setEndState(IState endState) {
        mEndState = endState;
        mAllStates.add(endState);
        mMapForAllStates.put(endState.getStateDesc(), new ArrayList<IState>());
    }

    @Override
    public void addState(IState startState, IState newState, Action action) {
        // validate startState, newState and action

        // update mapping in finite state machine
        mAllStates.add(newState);
        final String startStateDesc = startState.getStateDesc();
        final String newStateDesc = newState.getStateDesc();
        mMapForAllStates.put(newStateDesc, new ArrayList<IState>());
        ArrayList<IState> adjacentStateList = null;
        if (mMapForAllStates.containsKey(startStateDesc)) {
            adjacentStateList = mMapForAllStates.get(startStateDesc);
            adjacentStateList.add(newState);
        } else {
            mAllStates.add(startState);
            adjacentStateList = new ArrayList<>();
            adjacentStateList.add(newState);
        }
        mMapForAllStates.put(startStateDesc, adjacentStateList);

        // update mapping in startState
        for (IState state : mAllStates) {
            boolean isStartState = state.getStateDesc().equals(startState.getStateDesc());
            if (isStartState) {
                startState.addTransit(action, newState);
            }
        }
    }

    @Override
    public void removeState(String targetStateDesc) {
        // validate state
        if (!mMapForAllStates.containsKey(targetStateDesc)) {
            throw new RuntimeException("Don't have state: " + targetStateDesc);
        } else {
            // remove from mapping
            mMapForAllStates.remove(targetStateDesc);
        }

        // update all state
        IState targetState = null;
        for (IState state : mAllStates) {
            if (state.getStateDesc().equals(targetStateDesc)) {
                targetState = state;
            } else {
                state.removeTransit(targetStateDesc);
            }
        }

        mAllStates.remove(targetState);

    }

    @Override
    public IState getCurrentState() {
        return mCurrentState;
    }

    @Override
    public void transit(Action action) {
        if (mCurrentState == null) {
            throw new RuntimeException("Please setup start state");
        }
        Map<String, IState> localMapping = mCurrentState.getAdjacentStates();
        if (localMapping.containsKey(action.toString())) {
            mCurrentState = localMapping.get(action.toString());
        } else {
            throw new RuntimeException("No action start from current state");
        }
    }

    @Override
    public IState getStartState() {
        return mStartState;
    }

    @Override
    public IState getEndState() {
        return mEndState;
    }
}

例子：

public class example {

    public static void main(String[] args) {
        System.out.println("Finite state machine!!!");
        IState startState = new StateImpl("start");
        IState endState = new StateImpl("end");
        IFiniteStateMachine fsm = new FiniteStateMachineImpl();
        fsm.setStartState(startState);
        fsm.setEndState(endState);
        IState middle1 = new StateImpl("middle1");
        middle1.addTransit(new Action("path1"), endState);
        fsm.addState(startState, middle1, new Action("path1"));
        System.out.println(fsm.getCurrentState().getStateDesc());
        fsm.transit(new Action(("path1")));
        System.out.println(fsm.getCurrentState().getStateDesc());
        fsm.addState(middle1, endState, new Action("path1-end"));
        fsm.transit(new Action(("path1-end")));
        System.out.println(fsm.getCurrentState().getStateDesc());
        fsm.addState(endState, middle1, new Action("path1-end"));
    }

}

Github 上的完整示例