Skip to content

Latest commit

 

History

History
424 lines (296 loc) · 28 KB

README.md

File metadata and controls

424 lines (296 loc) · 28 KB
Raw

Artificial-Intelligence-Nanodegree

Introductory Project: Diagonal Sudoku Solver

Question 1 (Naked Twins)

Q: How do we use constraint propagation to solve the naked twins problem?
A: Constraint propagation is used to find identical boxes having same recommend digits and to reduce the search and complexity of the problem, later these recommend digits are then assigned to the boxes based on only choice available.

Question 2 (Diagonal Sudoku)

Q: How do we use constraint propagation to solve the diagonal sudoku problem?
A: Constraint propagation is also helpful in diagonal sudoku problem by adding diagonal to row, column and 3*3 square units, by this way diagonal also treated as peer for the box. Hence, during all used algorithms naked_twins, only_choice, eliminate applies on the diagonal too.

Install

This project requires Python 3.

We recommend students install Anaconda, a pre-packaged Python distribution that contains all of the necessary libraries and software for this project. Please try using the environment we provided in the Anaconda lesson of the Nanodegree.

Optional: Pygame

Optionally, you can also install pygame if you want to see your visualization. If you've followed our instructions for setting up our conda environment, you should be all set.

If not, please see how to download pygame here.

Code

  • solution.py - You'll fill this in as part of your solution.
  • solution_test.py - Do not modify this. You can test your solution by running python solution_test.py.
  • PySudoku.py - Do not modify this. This is code for visualizing your solution.
  • visualize.py - Do not modify this. This is code for visualizing your solution.

Visualizing

To visualize your solution, please only assign values to the values_dict using the assign_value function provided in solution.py

Submission

Before submitting your solution to a reviewer, you are required to submit your project to Udacity's Project Assistant, which will provide some initial feedback.

The setup is simple. If you have not installed the client tool already, then you may do so with the command pip install udacity-pa.

To submit your code to the project assistant, run udacity submit from within the top-level directory of this project. You will be prompted for a username and password. If you login using google or facebook, visit this link for alternate login instructions.

This process will create a zipfile in your top-level directory named sudoku-.zip. This is the file that you should submit to the Udacity reviews system.

Build a Game-playing Agent

Example game of isolation

Synopsis

In this project, students will develop an adversarial search agent to play the game "Isolation". Isolation is a deterministic, two-player game of perfect information in which the players alternate turns moving a single piece from one cell to another on a board. Whenever either player occupies a cell, that cell becomes blocked for the remainder of the game. The first player with no remaining legal moves loses, and the opponent is declared the winner. These rules are implemented in the isolation.Board class provided in the repository.

This project uses a version of Isolation where each agent is restricted to L-shaped movements (like a knight in chess) on a rectangular grid (like a chess or checkerboard). The agents can move to any open cell on the board that is 2-rows and 1-column or 2-columns and 1-row away from their current position on the board. Movements are blocked at the edges of the board (the board does not wrap around), however, the player can "jump" blocked or occupied spaces (just like a knight in chess).

Additionally, agents will have a fixed time limit each turn to search for the best move and respond. If the time limit expires during a player's turn, that player forfeits the match, and the opponent wins.

Students only need to modify code in the game_agent.py file to complete the project. Additional files include example Player and evaluation functions, the game board class, and a template to develop local unit tests.

Instructions

In order to complete the Isolation project, students must submit code that passes all test cases for the required functions in game_agent.py and complete a report as specified in the rubric. Students can submit using the Udacity Project Assistant command line utility. Students will receive feedback on test case success/failure after each submission.

Students must implement the following functions:

  • MinimaxPlayer.minimax(): implement minimax search
  • AlphaBetaPlayer.alphabeta(): implement minimax search with alpha-beta pruning
  • AlphaBetaPlayer.get_move(): implement iterative deepening search
  • custom_score(): implement your own best position evaluation heuristic
  • custom_score_2(): implement your own alternate position evaluation heuristic
  • custom_score_3(): implement your own alternate position evaluation heuristic

You may write or modify code within each file (but you must maintain compatibility with the function signatures provided). You may add other classes, functions, etc., as needed, but it is not required.

The Project Assistant sandbox for this project places some restrictions on the modules available and blocks calls to some of the standard library functions. In general, standard library functions that introspect code running in the sandbox are blocked, and the PA only allows the following modules random, numpy, scipy, sklearn, itertools, math, heapq, collections, array, copy, and operator. (Modules within these packages are also allowed, e.g., numpy.random.)

Quickstart Guide

The following example creates a game and illustrates the basic API. You can run this example by activating your aind anaconda environment and executing the command python sample_players.py

from isolation import Board
from sample_players import RandomPlayer
from sample_players import GreedyPlayer

# create an isolation board (by default 7x7)
player1 = RandomPlayer()
player2 = GreedyPlayer()
game = Board(player1, player2)

# place player 1 on the board at row 2, column 3, then place player 2 on
# the board at row 0, column 5; display the resulting board state.  Note
# that the .apply_move() method changes the calling object in-place.
game.apply_move((2, 3))
game.apply_move((0, 5))
print(game.to_string())

# players take turns moving on the board, so player1 should be next to move
assert(player1 == game.active_player)

# get a list of the legal moves available to the active player
print(game.get_legal_moves())

# get a successor of the current state by making a copy of the board and
# applying a move. Notice that this does NOT change the calling object
# (unlike .apply_move()).
new_game = game.forecast_move((1, 1))
assert(new_game.to_string() != game.to_string())
print("\nOld state:\n{}".format(game.to_string()))
print("\nNew state:\n{}".format(new_game.to_string()))

# play the remainder of the game automatically -- outcome can be "illegal
# move", "timeout", or "forfeit"
winner, history, outcome = game.play()
print("\nWinner: {}\nOutcome: {}".format(winner, outcome))
print(game.to_string())
print("Move history:\n{!s}".format(history))

Coding

The steps below outline a suggested process for completing the project -- however, this is just a suggestion to help you get started. A stub for writing unit tests is provided in the agent_test.py file (no local test cases are provided). (See the unittest module for information on getting started.)

The primary mechanism for testing your code will be the Udacity Project Assistant command line utility. You can install the Udacity-PA tool by activating your aind anaconda environment, then running pip install udacity-pa. You can submit your code for scoring by running udacity submit isolation. The project assistant server has a collection of unit tests that it will execute on your code, and it will provide feedback on any successes or failures. You must pass all test cases in the project assistant before you can complete the project by submitting your report for review.

  1. Verify that the Udacity-PA tool is installed properly by submitting the project. Run udacity submit isolation. (You should see a list of test cases that failed -- that's expected because you haven't implemented any code yet.)

  2. Modify the MinimaxPlayer.minimax() method to return any legal move for the active player. Resubmit your code to the project assistant and the minimax interface test should pass.

  3. Further modify the MinimaxPlayer.minimax() method to implement the full recursive search procedure described in lecture (ref. AIMA Minimax Decision). Resubmit your code to the project assistant and both the minimax interface and functional test cases will pass.

  4. Start on the alpha beta test cases. Modify the AlphaBetaPlayer.alphabeta() method to return any legal move for the active player. Resubmit your code to the project assistant and the alphabeta interface test should pass.

  5. Further modify the AlphaBetaPlayer.alphabeta() method to implement the full recursive search procedure described in lecture (ref. AIMA Alpha-Beta Search). Resubmit your code to the project assistant and both the alphabeta interface and functional test cases will pass.

  6. You can pass the interface test for the AlphaBetaPlayer.get_move() function by copying the code from MinimaxPlayer.get_move(). Resubmit your code to the project assistant to see that the get_move() interface test case passes.

  7. Pass the test_get_move test by modifying AlphaBetaPlayer.get_move() to implement Iterative Deepening. See Also AIMA Iterative Deepening Search

  8. Finally, pass the heuristic tests by implementing any heuristic in custom_score(), custom_score_2(), and custom_score_3(). (These test cases only validate the return value type -- it does not check for "correctness" of your heuristic.) You can see example heuristics in the sample_players.py file.

Tournament

The tournament.py script is used to evaluate the effectiveness of your custom heuristics. The script measures relative performance of your agent (named "Student" in the tournament) in a round-robin tournament against several other pre-defined agents. The Student agent uses time-limited Iterative Deepening along with your custom heuristics.

The performance of time-limited iterative deepening search is hardware dependent (faster hardware is expected to search deeper than slower hardware in the same amount of time). The script controls for these effects by also measuring the baseline performance of an agent called "ID_Improved" that uses Iterative Deepening and the improved_score heuristic defined in sample_players.py. Your goal is to develop a heuristic such that Student outperforms ID_Improved. (NOTE: This can be very challenging!)

The tournament opponents are listed below. (See also: sample heuristics and players defined in sample_players.py)

  • Random: An agent that randomly chooses a move each turn.
  • MM_Open: MinimaxPlayer agent using the open_move_score heuristic with search depth 3
  • MM_Center: MinimaxPlayer agent using the center_score heuristic with search depth 3
  • MM_Improved: MinimaxPlayer agent using the improved_score heuristic with search depth 3
  • AB_Open: AlphaBetaPlayer using iterative deepening alpha-beta search and the open_move_score heuristic
  • AB_Center: AlphaBetaPlayer using iterative deepening alpha-beta search and the center_score heuristic
  • AB_Improved: AlphaBetaPlayer using iterative deepening alpha-beta search and the improved_score heuristic

Submission

Before submitting your solution to a reviewer, you are required to submit your project to Udacity's Project Assistant, which will provide some initial feedback.

Please see the instructions in the AIND-Sudoku project repository for installation and setup instructions.

To submit your code to the project assistant, run udacity submit isolation from within the top-level directory of this project. You will be prompted for a username and password. If you login using google or facebook, follow the instructions for using a jwt.

This process will create a zipfile in your top-level directory named isolation-<id>.zip. This is the file that you should submit to the Udacity reviews system.

Game Visualization

The isoviz folder contains a modified version of chessboard.js that can animate games played on a 7x7 board. In order to use the board, you must run a local webserver by running python -m http.server 8000 from your project directory (you can replace 8000 with another port number if that one is unavailable), then open your browser to http://localhost:8000 and navigate to the /isoviz/display.html page. Enter the move history of an isolation match (i.e., the array returned by the Board.play() method) into the text area and run the match. Refresh the page to run a different game. (Feel free to submit pull requests with improvements to isoviz.)

PvP Competition

Once your project has been reviewed and accepted by meeting all requirements of the rubric, you are invited to complete the competition_agent.py file using any combination of techniques and improvements from lectures or online, and then submit it to compete in a tournament against other students from your cohort and past cohort champions. Additional details (official rules, submission deadline, etc.) will be provided separately.

The competition agent can be submitted using the Udacity project assistant:

udacity submit isolation-pvp

Implement a Planning Search

Synopsis

This project includes skeletons for the classes and functions needed to solve deterministic logistics planning problems for an Air Cargo transport system using a planning search agent. With progression search algorithms like those in the navigation problem from lecture, optimal plans for each problem will be computed. Unlike the navigation problem, there is no simple distance heuristic to aid the agent. Instead, you will implement domain-independent heuristics. Progression air cargo search

  • Part 1 - Planning problems:
    • READ: applicable portions of the Russel/Norvig AIMA text
    • GIVEN: problems defined in classical PDDL (Planning Domain Definition Language)
    • TODO: Implement the Python methods and functions as marked in my_air_cargo_problems.py
    • TODO: Experiment and document metrics
  • Part 2 - Domain-independent heuristics:
    • READ: applicable portions of the Russel/Norvig AIMA text
    • TODO: Implement relaxed problem heuristic in my_air_cargo_problems.py
    • TODO: Implement Planning Graph and automatic heuristic in my_planning_graph.py
    • TODO: Experiment and document metrics
  • Part 3 - Written Analysis

Environment requirements

  • Python 3.4 or higher
  • Starter code includes a copy of companion code from the Stuart Russel/Norvig AIMA text.

Project Details

Part 1 - Planning problems

READ: Stuart Russel and Peter Norvig text:

"Artificial Intelligence: A Modern Approach" 3rd edition chapter 10 or 2nd edition Chapter 11 on Planning, available on the AIMA book site sections:

  • The Planning Problem
  • Planning with State-space Search

GIVEN: classical PDDL problems

All problems are in the Air Cargo domain. They have the same action schema defined, but different initial states and goals.

  • Air Cargo Action Schema:
Action(Load(c, p, a),
	PRECOND: At(c, a) ∧ At(p, a) ∧ Cargo(c) ∧ Plane(p) ∧ Airport(a)
	EFFECT: ¬ At(c, a) ∧ In(c, p))
Action(Unload(c, p, a),
	PRECOND: In(c, p) ∧ At(p, a) ∧ Cargo(c) ∧ Plane(p) ∧ Airport(a)
	EFFECT: At(c, a) ∧ ¬ In(c, p))
Action(Fly(p, from, to),
	PRECOND: At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to)
	EFFECT: ¬ At(p, from) ∧ At(p, to))
  • Problem 1 initial state and goal:
Init(At(C1, SFO) ∧ At(C2, JFK) 
	∧ At(P1, SFO) ∧ At(P2, JFK) 
	∧ Cargo(C1) ∧ Cargo(C2) 
	∧ Plane(P1) ∧ Plane(P2)
	∧ Airport(JFK) ∧ Airport(SFO))
Goal(At(C1, JFK) ∧ At(C2, SFO))
  • Problem 2 initial state and goal:
Init(At(C1, SFO) ∧ At(C2, JFK) ∧ At(C3, ATL) 
	∧ At(P1, SFO) ∧ At(P2, JFK) ∧ At(P3, ATL) 
	∧ Cargo(C1) ∧ Cargo(C2) ∧ Cargo(C3)
	∧ Plane(P1) ∧ Plane(P2) ∧ Plane(P3)
	∧ Airport(JFK) ∧ Airport(SFO) ∧ Airport(ATL))
Goal(At(C1, JFK) ∧ At(C2, SFO) ∧ At(C3, SFO))
  • Problem 3 initial state and goal:
Init(At(C1, SFO) ∧ At(C2, JFK) ∧ At(C3, ATL) ∧ At(C4, ORD) 
	∧ At(P1, SFO) ∧ At(P2, JFK) 
	∧ Cargo(C1) ∧ Cargo(C2) ∧ Cargo(C3) ∧ Cargo(C4)
	∧ Plane(P1) ∧ Plane(P2)
	∧ Airport(JFK) ∧ Airport(SFO) ∧ Airport(ATL) ∧ Airport(ORD))
Goal(At(C1, JFK) ∧ At(C3, JFK) ∧ At(C2, SFO) ∧ At(C4, SFO))

TODO: Implement methods and functions in my_air_cargo_problems.py

  • AirCargoProblem.get_actions method including load_actions and unload_actions sub-functions
  • AirCargoProblem.actions method
  • AirCargoProblem.result method
  • air_cargo_p2 function
  • air_cargo_p3 function

TODO: Experiment and document metrics for non-heuristic planning solution searches

  • Run uninformed planning searches for air_cargo_p1, air_cargo_p2, and air_cargo_p3; provide metrics on number of node expansions required, number of goal tests, time elapsed, and optimality of solution for each search algorithm. Include the result of at least three of these searches, including breadth-first and depth-first, in your write-up (breadth_first_search and depth_first_graph_search).
  • If depth-first takes longer than 10 minutes for Problem 3 on your system, stop the search and provide this information in your report.
  • Use the run_search script for your data collection: from the command line type python run_search.py -h to learn more.

Why are we setting the problems up this way?

Progression planning problems can be solved with graph searches such as breadth-first, depth-first, and A*, where the nodes of the graph are "states" and edges are "actions". A "state" is the logical conjunction of all boolean ground "fluents", or state variables, that are possible for the problem using Propositional Logic. For example, we might have a problem to plan the transport of one cargo, C1, on a single available plane, P1, from one airport to another, SFO to JFK. state space In this simple example, there are five fluents, or state variables, which means our state space could be as large as 2to5. Note the following:

  • While the initial state defines every fluent explicitly, in this case mapped to TTFFF, the goal may be a set of states. Any state that is True for the fluent At(C1,JFK) meets the goal.
  • Even though PDDL uses variable to describe actions as "action schema", these problems are not solved with First Order Logic. They are solved with Propositional logic and must therefore be defined with concrete (non-variable) actions and literal (non-variable) fluents in state descriptions.
  • The fluents here are mapped to a simple string representing the boolean value of each fluent in the system, e.g. TTFFTT...TTF. This will be the state representation in the AirCargoProblem class and is compatible with the Node and Problem classes, and the search methods in the AIMA library.

Part 2 - Domain-independent heuristics

READ: Stuart Russel and Peter Norvig text

"Artificial Intelligence: A Modern Approach" 3rd edition chapter 10 or 2nd edition Chapter 11 on Planning, available on the AIMA book site section:

  • Planning Graph

TODO: Implement heuristic method in my_air_cargo_problems.py

  • AirCargoProblem.h_ignore_preconditions method

TODO: Implement a Planning Graph with automatic heuristics in my_planning_graph.py

  • PlanningGraph.add_action_level method
  • PlanningGraph.add_literal_level method
  • PlanningGraph.inconsistent_effects_mutex method
  • PlanningGraph.interference_mutex method
  • PlanningGraph.competing_needs_mutex method
  • PlanningGraph.negation_mutex method
  • PlanningGraph.inconsistent_support_mutex method
  • PlanningGraph.h_levelsum method

TODO: Experiment and document: metrics of A* searches with these heuristics

  • Run A* planning searches using the heuristics you have implemented on air_cargo_p1, air_cargo_p2 and air_cargo_p3. Provide metrics on number of node expansions required, number of goal tests, time elapsed, and optimality of solution for each search algorithm and include the results in your report.
  • Use the run_search script for this purpose: from the command line type python run_search.py -h to learn more.

Why a Planning Graph?

The planning graph is somewhat complex, but is useful in planning because it is a polynomial-size approximation of the exponential tree that represents all possible paths. The planning graph can be used to provide automated admissible heuristics for any domain. It can also be used as the first step in implementing GRAPHPLAN, a direct planning algorithm that you may wish to learn more about on your own (but we will not address it here).

Planning Graph example from the AIMA book Planning Graph

Part 3: Written Analysis

TODO: Include the following in your written analysis.

  • Provide an optimal plan for Problems 1, 2, and 3.
  • Compare and contrast non-heuristic search result metrics (optimality, time elapsed, number of node expansions) for Problems 1,2, and 3. Include breadth-first, depth-first, and at least one other uninformed non-heuristic search in your comparison; Your third choice of non-heuristic search may be skipped for Problem 3 if it takes longer than 10 minutes to run, but a note in this case should be included.
  • Compare and contrast heuristic search result metrics using A* with the "ignore preconditions" and "level-sum" heuristics for Problems 1, 2, and 3.
  • What was the best heuristic used in these problems? Was it better than non-heuristic search planning methods for all problems? Why or why not?
  • Provide tables or other visual aids as needed for clarity in your discussion.

Examples and Testing:

  • The planning problem for the "Have Cake and Eat it Too" problem in the book has been implemented in the example_have_cake module as an example.
  • The tests directory includes unittest test cases to evaluate your implementations. All tests should pass before you submit your project for review. From the AIND-Planning directory command line:
    • python -m unittest tests.test_my_air_cargo_problems
    • python -m unittest tests.test_my_planning_graph
  • The run_search script is provided for gathering metrics for various search methods on any or all of the problems and should be used for this purpose.

Submission

Before submitting your solution to a reviewer, you are required to submit your project to Udacity's Project Assistant, which will provide some initial feedback.

The setup is simple. If you have not installed the client tool already, then you may do so with the command pip install udacity-pa.

To submit your code to the project assistant, run udacity submit from within the top-level directory of this project. You will be prompted for a username and password. If you login using google or facebook, visit this link for alternate login instructions.

This process will create a zipfile in your top-level directory named cargo_planning-.zip. This is the file that you should submit to the Udacity reviews system.

Improving Execution Time

The exercises in this project can take a long time to run (from several seconds to a several hours) depending on the heuristics and search algorithms you choose, as well as the efficiency of your own code. (You may want to stop and profile your code if runtimes stretch past a few minutes.) One option to improve execution time is to try installing and using pypy3 -- a python JIT, which can accelerate execution time substantially. Using pypy is not required (and thus not officially supported) -- an efficient solution to this project runs in very reasonable time on modest hardware -- but working with pypy may allow students to explore more sophisticated problems than the examples included in the project.

Artificial Intelligence Engineer Nanodegree

Probabilistic Models

Project: Sign Language Recognition System

Install

This project requires Python 3 and the following Python libraries installed:

Notes:

  1. It is highly recommended that you install the Anaconda distribution of Python and load the environment included in the "Your conda env for AI ND" lesson.
  2. The most recent development version of hmmlearn, 0.2.1, contains a bugfix related to the log function, which is used in this project. In order to install this version of hmmearn, install it directly from its repo with the following command from within your activated Anaconda environment:
pip install git+https://github.com/hmmlearn/hmmlearn.git

Code

A template notebook is provided as asl_recognizer.ipynb. The notebook is a combination tutorial and submission document. Some of the codebase and some of your implementation will be external to the notebook. For submission, complete the Submission sections of each part. This will include running your implementations in code notebook cells, answering analysis questions, and passing provided unit tests provided in the codebase and called out in the notebook.

Run

In a terminal or command window, navigate to the top-level project directory AIND_recognizer/ (that contains this README) and run one of the following command:

jupyter notebook asl_recognizer.ipynb

This will open the Jupyter Notebook software and notebook in your browser which is where you will directly edit and run your code. Follow the instructions in the notebook for completing the project.

Additional Information

Provided Raw Data

The data in the asl_recognizer/data/ directory was derived from the RWTH-BOSTON-104 Database. The handpositions (hand_condensed.csv) are pulled directly from the database boston104.handpositions.rybach-forster-dreuw-2009-09-25.full.xml. The three markers are:

  • 0 speaker's left hand
  • 1 speaker's right hand
  • 2 speaker's nose
  • X and Y values of the video frame increase left to right and top to bottom.

Take a look at the sample ASL recognizer video to see how the hand locations are tracked.

The videos are sentences with translations provided in the database.
For purposes of this project, the sentences have been pre-segmented into words based on slow motion examination of the files.
These segments are provided in the train_words.csv and test_words.csv files in the form of start and end frames (inclusive).

The videos in the corpus include recordings from three different ASL speakers. The mappings for the three speakers to video are included in the speaker.csv file.