Please enable JavaScript.
Coggle requires JavaScript to display documents.
Goal-based Agent - Pathfinding, Goal-based Agents-pathfinding - Coggle…
Goal-based Agent - Pathfinding
Pathfinding
Pathfinding is the process of determining a route or path between two points in a graph, network, or grid. It is essential in various applications like robotics, gaming, and navigation systems, where finding the most efficient way to reach a destination is crucial
Resources
Google.com. (2024). pathfinding definition - Google Search. [online] Available at:
https://www.google.com/search?q=+pathfinding+definition
. (Google.com, 2024)
Rubio, F. (2023). Pathfinding Algorithms- Top 5 Most Powerful. [online] www.graphable.ai. Available at:
https://www.graphable.ai/blog/pathfinding-algorithms/.(Rubio
, 2023)
Data Structures Handbook. (n.d.). Graphs. [online] Available at:
https://www.thedshandbook.com/graphs/.(Data
Structures Handbook, n.d.)
Simplilearn (2021). A* Algorithm in Artificial Intelligence You Must Know in 2022. [online] Simplilearn.com. Available at:
https://www.simplilearn.com/tutorials/artificial-intelligence-tutorial/a-star-algorithm.(Simplilearn
, 2021)
FSM
A finite state machine is a computation model that can be implemented with hardware or software and can be used to simulate sequential logic and some computer programs. Finite state automata generate regular languages. Finite state machines can be used to model problems in many fields including mathematics, artificial intelligence, games, and linguistics..
Types of FSM
Mealy machine
Where the output values are determined based on the current state together with the current input
Moore machine
Where the output is determined solely based on the current state
FSM examples
Vending machine
states: coin inserted button pressed
Traffic lights
state: red, yellow, green
Elevators
based on the buttons
pressed by passengers
FSM in various fields
Logistics
Analyzing language structure
Mathematics
Studying automated theory
AI
Designing intelligent systems
Games
implementing game logic and character behavior
Computer science
modeling computer programs
Network
Goal-based agents often operate within pathfinding networks, which are essentially maps or representations of the environment where the agent needs to navigate.
network types
Directed
connection between this nodes are directed
Undirected
Weighted
Different distance, time to move between two locations
Unweighted
One step or until of distance
Graph-based networks
Nodes
represent positions, states in the environment (location on a map)
Edges
represent possible movements between nodes
Examples
Topography
Website index circuits
Tile based games
A electric circuit diagram
BFS
(Breadth first search)
Begin the search at the initial node
Mark the current node as visited
Add all visited neighbors to a queue
Remove the first node from the queue and repeat the process with its neighbor
Repeat until all nodes have been visitor or the goal is find
DFS
(Depth first search)
Follow each node to its limit
Reverse when dead end
Dive deeply into the graph's structure
Continue forward if there are unexplored nodes
Example
The algorithm explores as far as possible along each branch before backtracking. This approach makes it an ideal choice for various tasks, including pathfinding, cycle detection, and more.
A* Search
A* (A-Star) is a popular choice for pathfinding because it combines the strengths of Dijkstra's algorithm and Greedy Best-First Search, making it efficient and optimal. It uses a heuristic function to evaluate paths by balancing the cost to reach a node (g-cost) and the estimated cost to the goal (h-cost).
Applications
In robotic
Helps robots navigate/ find optimal path
In video games
It enables NPC ( non-player characters) to navigate game environment
Logistics industries
vehicle routing and scheduling
Routing planning
find the shortest or fastest routes between locations
Digraph (Directed graph where edges have a direction)
Optimality
If the agent requires the shortest
Efficiency
In real-time applications, efficiency is key to avoid excessive computation
Exploration
In some scenarios, the agent may need to explore all possible paths or alternatives before reaching the goal.
Goal-based Agents-pathfinding
