Skip to content

Java implementation of algorithms from Norvig And Russell's "Artificial Intelligence - A Modern Approach"

License

Notifications You must be signed in to change notification settings

KShirokov/aima-java

 
 

Repository files navigation

AIMA4e-Java (JDK 8+) Build Status

Java implementation of algorithms from Norvig And Russell's "Artificial Intelligence - A Modern Approach 4th Edition."


NOTE: This is an in progress complete rewrite of the algorithms, leveraging JDK 8's new language features, from the AIMA3e branch (currently master branch)


Index of Implemented Algorithms

Fig Page Name (in book) Code
2.1 35 Agent Agent
2.3 36 Table-Driven-Vacuum-Agent TableDrivenVacuumAgent
2.7 47 Table-Driven-Agent TableDrivenAgent
2.8 48 Reflex-Vacuum-Agent ReflexVacuumAgent
2.10 49 Simple-Reflex-Agent SimpleReflexAgent
2.12 51 Model-Based-Reflex-Agent ModelBasedReflexAgent
3 66 Problem Problem
3.1 67 Simple-Problem-Solving-Agent SimpleProblemSolvingAgent
3.2 68 Romania SimplifiedRoadMapOfPartOfRomania
3.7 77 Tree-Search GeneralTreeSearch
3.7 77 Graph-Search GeneralGraphSearch
3.10 79 Node Node
3.11 82 Breadth-First-Search BreadthFirstGraphSearch
3.14 84 Uniform-Cost-Search UniformCostGraphSearch
3 85 Depth-first Search BasicDepthFirstGraphSearch
3.17 88 Depth-Limited-Search RecursiveDepthLimitedTreeSearch
3.18 89 Iterative-Deepening-Search IterativeDeepeningSearch
3 92 Best-First search BestFirstGraphSearch
3 92 Greedy best-First search GreedyBestFirstGraphSearch
3 93 A* Search AStarGraphSearch
3.26 99 Recursive-Best-First-Search RecursiveBestFirstTreeSearch

TODO (REMEMBER - KEEP IT SIMPLE SIMPLE SIMPLE!!!! :)

CURRENT (new demo GUI)

  • Re-design uninformed and informed search hierarchy:
    • SearchFunction
      • TreeSearch (sub-package)
        • GeneralTreeSearch (fig 3.7) x
          • BasicGeneralTreeSearch x
            • BasicDepthFirstTreeSearch (pg. 86 'modified at no extra memory cost so that it checks new states against those on the path from the root to the current node; to avoid infinite loops)
          • UniformCostTreeSearch (ensure does not need to be at same level as GeneralTreeSearch)
            • BasicUniformCostTreeSearch
        • BreadthFirstTreeSearch (variant of General tree search which checks if solution before adding to frontier)
          • BasicBreadthFirstTreeSearch
        • recursive
          • RecursiveDepthLimitedTreeSearch (fig 3.17) x
            • BasicRecursiveDepthLimitedTreeSearch x
          • IterariveDeepeningSearch x
            • BasicIterativeDeepeningSearch x
          • RecursiveBestFirstTreeSearch (fig 3.26) x
            • BasicRecursiveBestFirstTreeSearch x
        • BestFirstTreeSearch (pg 92)
          • GreedyBestFirstTreeSearch
            • BasicGreedyBestFirstTreeSearch
          • AStarTreeSearch
            • BasicAStarTreeSearch
      • GraphSearch (Marker Interface or sub-package)
        • GeneralGraphSearch (fig 3.7) x
          • BasicGeneralGraphSearch x
            • BasicDepthFirstGraphSearch x
        • BreadthFirstGraphSearch (fig 3.11) x
          • BasicBreadthFirstGraphSearch x
        • UniformCostGraphSearch (fig 3.14) x
          • BasicUniformCostGraphSearch x
        • BestFirstGraphSearch (pg 92 - implementation identical to fig 3.14 except for cost) x
          • GreedyBestFirstGraphSearch x
            • BasicGreedyBestFirstGraphSearch x
          • AStartGraphSearch x
            • BasicAStartGraphSearch x
  • Tree-Search demo
    • Add additional tree search algorithms to simulate
    • Add visualizations specific to recursive tree search algorithms
    • Configure rectangular problem
      • Change size of grid
      • Specify order of actions.
        • Clockwise
        • Anti-Clockwise
        • Random
          • Check box for 'each time' new random sequence.
        • User Selected (via groups of toggle buttons).
    • Add additional problems
      • Binary search tree (i.e. fig 3.12 and also take into account fig 3.16)
        • Possibly show before Rectangular problem in demo
      • 2D Map (i.e. Map of Romania)
        • A* display contours (fig 3.25)
      • Informed search
        • Display heuristic information summary pane (fig 3.22)
  • Graph-Search demo
    • Summary information related to explored set.
  • GUI demo
    • Mark each algorithm (search) with icons indicating complexity, optimality, time and space complexity (chp 3 pg 80 and fig 3.21).

LATER

Chapter 3 'core' module.

  • Uniform-Cost-Search need a better mechanism for determining state containment in the queue and remove a node with a higher state cost.
  • Recursive-Best-First-Search - look to improve/tidy up implementation.
  • BasicRecursiveBestFirstSearchTest
  • 3 90 Bidirectional search
  • BasicBestFirstGraphSearchTest
  • BasicGreedyestFirstGraphSearchTest
  • BasicAStarGraphSearchTest
  • BasicIterativeDeepeningSearchTest
  • BasicDepthLimitedSearchTest
  • BasicDepthFirstSearchTest
  • BasicUniformCostSearchTest
  • BreadthFirstSearchTest - additional tests.
  • BasicGraphSearchTest
  • BasicTreeSearchTest
  • BasicProblemTest
  • BasicSimpleProblemSolvingAgentTest

Chapter 2 'core' module.

  • BasicModelBasedReflexAgentTest
  • BasicTableDrivenAgentTest

Chapter 2 'extra' module.

  • Environment defintion: Consider specifying Dimensions in API, see pg. 42.
  • Environment Simulator referenced on pg. 45 (this will be a refactor of the a lot of the environment stuff in aima3e-core).

USEFUL RESOURCES

GUI

About

Java implementation of algorithms from Norvig And Russell's "Artificial Intelligence - A Modern Approach"

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages

  • Java 99.9%
  • HTML 0.1%