Transcript finite state machine (FSM) - School of Science and Technology

AI Perspective
Topic
•
•
•
•
•
Finite State Machine [FSM]
Artificial Stupidity
Game of Life
Swarm Intelligent (Ant Colony, Flocking)
Scripting
Finite State Machine [FSM]
• A finite state machine (FSM)
or finite state automaton
(plural: automata) or simply a
state machine, is a model of
behavior composed of a finite
number of states, transitions
between those states, and
actions. A finite state machine is
an abstract model of a machine
with a primitive internal
memory
http://en.wikipedia.org/wiki/Finite_state_machine
Finite State Machine [FSM]
Where to use? AI's mind,
Event triggers in game.
•
่ ?
พลังเพิม
่ ?
เู ้ ลน
ตืน
่
ห็นผ
หล ับ
มองเ
่
น
็นผเู ้ ล
ห
่
เ
ม
ไ
มอง
หนี
?
เข ้าใกล ้?
มองไม่เห็นผู ้เล่น?
ต่อสู ้
รอ?
งั ล
พล
ง?
ล
ด
พลังหมด?
พลังหมด?
เกิดใหม่
ตาย
มีโควต ้า?
Drop Items..
Game of Life
• 1D Cellular automaton
• 2D Conway's Game of Life
• Applications
Artificial Stupidity
Artificial Stupidity is commonly used as a
humorous opposite of the term artificial
intelligence (AI), often as a derogatory reference
to the inability of an AI program to adequately
perform basic tasks. However, within the field of
computer science, artificial stupidity is also used to
refer to a technique of "dumbing down" computer
programs in order to deliberately introduce errors
in their responses.
http://en.wikipedia.org/wiki/Artificial_stupidity
Artificial Stupidity
Applications
• finely tuning the level of "artificial
stupidity", it is possible to create
computer controlled plays that allow
the player to win, but do so "without
looking unintelligent".[
• Artificial Stupidity program would be
able to make all the worst cases
regarding a given situation
http://en.wikipedia.org/wiki/Artificial_stupidity
Case Study: IBM Develops Artificial
Stupidity
• Matthew writes: IBM researchers today announced that they have
developed a software agent that passes the Turing test. The Turing
test states that software is artificially intelligent when reasonable
humans cannot tell that they are communicating with a computer.
They did this by incorporating a new technology called “Artificial
Stupidity” or AS.
• Code-named “Anna Nicole”, the software agent interfaces with
real people constantly via a special AOL Instant Message interface
and an E! Television show. AOL Instant Messages are the
computer’s only bi-directional interface with the outside world.
The software runs on IBM’s famous Deep Blue computer, but now
takes so little compute power that a port to Linux is in the works.
•
Posted by Matthew on Wednesday September 4, 2002 @05:16PM
http://www.slashnot.com/articles/67/
Cellular automaton
• A cellular automaton (plural:
cellular automata) is a discrete
model studied in computability
theory, mathematics, theoretical
biology and microstructure
modeling. It consists of a regular
grid of cells, each in one of a
finite number of states.
http://en.wikipedia.org/wiki/Cellular_automata
Rule 30CA
Conway's Game of Life
The universe of the Game of Life is an
infinite two-dimensional orthogonal
grid of square cells, each of which is
in one of two possible states, live or
dead. Every cell interacts with its
eight neighbours, which are the cells
that are directly horizontally,
vertically, or diagonally adjacent.
http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
Conway's Game of Life
Rules
• Any live cell with fewer than two live neighbours
dies, as if by needs caused by underpopulation.
• Any live cell with more than three live neighbours
dies, as if by overcrowding.
• Any live cell with two or three live neighbours
lives, unchanged, to the next generation.
• Any dead cell with exactly three live neighbours
becomes a live cell.
http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
Applications
glider generator
lwss
switch engine
http://www.ericweisstein.com/encyclopedias/life/SwitchEngine.html
glider
A sample of a 48-step oscillator
along with a 2-step oscillator
and a 3-step oscillator from a
2D hexagonal Game of Life (rule
34/2).
Swarm Intelligence [SI]
• SI systems are typically made up of a population of simple
agents interacting locally with one another and with their
environment. The agents follow very simple rules, and
although there is no centralized control structure dictating
how individual agents should behave, local, and to a
certain degree random, interactions between such agents
lead to the emergence of "intelligent" global behavior,
unknown to the individual agents. Natural examples of SI
include ant colonies, bird flocking, animal herding,
bacterial growth, and fish schooling.
• Swarm = ฝูง
• รวมกันเราอยู่ -- แยกหมู่ตายเดี่ยว
http://en.wikipedia.org/wiki/Swarm_intelligence
SI: bird flocking, fish schooling
Basic flocking is controlled by three simple rules:
• Separation - avoid crowding neighbours (short
range repulsion) หลบการชนกัน ไม่เบียดกันมากเกินไป
• Alignment - steer towards average heading of
neighbours จัดเรี ยงให้เป็ นแถวเป็ นแนว
• Cohesion - steer towards average position of
neighbours (long range attraction) พยายามอยูใ่ นตาแหน่ง
ที่ประสานกัน
Bird Flocking
Fish Schooling
War flocking
Sun Quan + Lui Bei
vs. Cao Cao
80,000
ชนะ
1,000,000
red cliff
Slime Mold solved Puzzle Maze
• In 2000 the 18th First
Annual Ig Nobel Prize
• Pieces of the slime mould
were enticed through a 30square-centimeter
• Toshiyuki Nakagaki
claimed to have found the
slime mold Physarum
polycephalum is capable of
finding the shortest way
through a maze
http://twistedphysics.typepad.com/cocktail_party_physics/biophysics/
http://www.daviddarling.info/encyclopedia/S/slime_mold.html
SI: ant colony
• ant colony optimization (aco)
trail pheromone
http://en.wikipedia.org/wiki/Ant_colony_optimization
http://alwaysrun.wordpress.com/2008/05/22/ant-colony-optimization-aco-algorithm/
aco
http://www.nightlab.ch/antsim.php
see movie :
Scripting