Edited by lrh9, 05 June 2012 - 03:42 AM.
0
4 replies to this topic
#1 Members - Reputation: 114
Posted 05 June 2012 - 03:39 AM
I've been reading about finite state machines, and - as I understand it - they can be represented by graphs. I wonder if FSMs implemented on a graph data structure would have any special or unique practical applications. I have a gut feeling that finding paths between two states and finding predecessors or successors of a given state might have practical applications, but I can't imagine any detailed use cases. I could see finding the shortest path between two states as a way to determine the minimal set of states an actor must traverse when going from one state to another, and I could see predecessors or successors used to enable systems to reason about the previous and next states of a system based on the current state. Thoughts?
Sponsor:
#2 Members - Reputation: 156
Posted 05 June 2012 - 12:22 PM
A FSM graph is the same thing than a chunk of code, where your transition rules are the IFs, your cycles are your FORs & WHILEs and nodes are procedural chunks of code, or basic blocks (look it up).
The similarities are most obvious when you look at code to parse computer language grammars, like say, a java parser. A parser generated by yacc/bison would generate a traditional table based FSM while a recursively descent parser generated by, say, CoCo/R or a human, would look like traditional code.
Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.
The similarities are most obvious when you look at code to parse computer language grammars, like say, a java parser. A parser generated by yacc/bison would generate a traditional table based FSM while a recursively descent parser generated by, say, CoCo/R or a human, would look like traditional code.
Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.
#3 Crossbones+ - Reputation: 3309
Posted 05 June 2012 - 12:37 PM
Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.
I'm sorry Lisp is out of the office right now. But if you can please leave a message, it'll get back to you with that self-evaluating and self-evolving program at its earliest convenience.
Edited by Alpha_ProgDes, 05 June 2012 - 12:38 PM.
Beginner in Game Development? Read here.
Super Mario Bros clone tutorial written in XNA 4.0 [MonoGame, ANX, and MonoXNA] by Scott Haley
If you have found any of the posts helpful, please show your appreciation by clicking the up arrow on those posts 
Spoiler
#4 Moderators - Reputation: 7772
Posted 05 June 2012 - 12:51 PM
Could you represent a practical FSM as a graph data structure? Sure. But why would you want to?
Most FSMs in practice are just simple transition logic around a lot of interesting state logic. There's not much purpose to building a "framework" there unless you want to make a visual FSM editing tool for designers or something similar; even that has limited usefulness in my experience, because designing the states and transitions is the borderline-trivial part of doing FSM-based AI. The interesting part is implementing the state logic and doing the correct reasoning to invoke the transitions.
Just looking at a pretty graph structure doesn't really give you that much insight into what a FSM implementation is all about.
Most FSMs in practice are just simple transition logic around a lot of interesting state logic. There's not much purpose to building a "framework" there unless you want to make a visual FSM editing tool for designers or something similar; even that has limited usefulness in my experience, because designing the states and transitions is the borderline-trivial part of doing FSM-based AI. The interesting part is implementing the state logic and doing the correct reasoning to invoke the transitions.
Just looking at a pretty graph structure doesn't really give you that much insight into what a FSM implementation is all about.
Maker of Machinery
[Work - ArenaNet] [Epoch Language] [Scribblings] [Journal - peek into my shattered mind]
[Work - ArenaNet] [Epoch Language] [Scribblings] [Journal - peek into my shattered mind]
#5 Members - Reputation: 156
Posted 05 June 2012 - 01:24 PM
There is no way a Lisp program would achieve intelligence without human intervention and I am still waiting after so many decades.
Rule evaluation != reasoning.
Your point being?
Rule evaluation != reasoning.
Asking if a graph algorithm can automatically reason is like asking if there is an algorithm to make the computer self program without human intervention.
I'm sorry Lisp is out of the office right now. But if you can please leave a message, it'll get back to you with that self-evaluating and self-evolving program at its earliest convenience.
Your point being?
