OldCourseAssignments

ASSIGNMENT #2

due date: Wednesday Nov 5th 11:59pm (was Monday Nov 3rd, 5pm).

problem #1: deductive reasoning agent: (7 marks) Create a RoboCup agent that uses either an expert system or a planner or a theorem prover or an AND-OR tree. You must use sample code from the AI textbook [4]. You are NOT allowed (i.e., you get a ZERO for this question if you do!) to implement your own planner or theorem prover or... etc (as history indicates that nearly every such attempt in such short time has ended up in failure!). Note that the agent doesn't need to really play soccer; all it needs to do is exhibit the fact that it can take the input from the Soccer Server, use the reasoning algorithm, and do something meaningful. To show that your agent is indeed reasoning and not just reacting:

if you use a planner, the resulting plan to execute should involve at minimum 2 STRIPS operators;
if you use an expert system, the forward or backward chaining engine should chain at minimum 2 rules;
if you use a theorem prover, at least one proof should have a depth of at minimum 2 steps;
if you use an AND-OR tree, the solution contingency tree should have a depth of at minimum 2.

As in assignment 1, give a one page description of your approach: the justification for your choice, the input you used, the output of the algorithm (showing that you addressed the "minimum 2" rule above), how to run your code, what is the code doing, etc. Get your program to output to the console what is happening during execution (tree being generated and followed, rule being executed, proof obtained, plan generated and followed, etc.): this should help you debug what's happening and helps me understand it better too. Only Java code is accepted. I should be able to run your code just like I run Krislet. Code that is hard to compile and/or run will lead to severe mark deduction.

problem #2: agent in an uncertain environment: (3 marks) Now suppose that the soccer-playing agent has to choose between 2 or more actions, where the outcome of the actions on certain factors (those that determine the welfare of the agent) is uncertain.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies among various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show (i.e., calculate and show your work!) how the introduction of evidence about the environment (i.e., P(X|A,e) vs P(X|A)) changes the choice of the action that the agent will make. (note that this means that your hand-crafted probabilities should be such that the choice of the agent does change with the introduction of evidence)

2 pages max!

Bundle your code and documentation for Q1 and the answer to Q2 in a zip file and submit on Brightspace. Any diagrams must be included directly in the document. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: Monday September 29th, 5pm.

1- Come up with a reactive soccer-playing agent for RoboCup, as per the definition of a reactive agent found in the Wooldridge book. Use Krislet as the starting point for your code. The agent function, i.e. the mapping between the environment state and the action, should be stored in an editable text file separate from the code. One should be able to modify the behavior of your agent by simply editing the text file and without recompiling your code. In a short accompanying document (about half a page and up to a page) tell us how to read, edit and make sense of your agent function definition, give a formal definition of YOUR function (i.e., as applied to your solution) as well a brief intelligible description, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code.

2- Now come up with a state-based soccer-playing agent. Ideally, the behaviour of the agent (i.e., the Mealy machine) should again be stored in an editable text file separate from the code, but we're also ok with a hard-coded state machine as long as it is easy to modify it. Again, in a short accompanying document (up to a page or two this time) tell us how to read, edit and make sense of your agent function definition, provide a human-readable Mealy machine diagram (in the extended UML FSM format discussed in class) corresponding to your implementation, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code. In addition, the guide should PROVE, using runs derived manually from the state machine or from logs obtained from running the agent, that the behaviour is indeed state-based and not reactive.

For each part of the assignment, bundle your code and your guide in a separate zip file (only the ZIP format will be accepted, not 7z, RAR or other), just like the zip bundle we provided you that contains Krislet and the RoboCup server and monitor. So basically your code should go where the Krislet folder is. I should be able to run your code just like I run Krislet. Store your accompanying document at the top level of the folder hierarchy. Submit your two zip files on Brightspace.

All questions will be judged by the neatness, correctness, usability (the code should be very easy to run, which probably means it should run the same way Krislet is run) and reusability (the behaviors should be easy to edit) of the description, code and approach. Don't forget to address all the questions that were asked!

Do not exceed the page limits. Do not hand-draw diagrams. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

Hint: do not make things more complicated than they need to be. We don't expect an agent that plays well. We just want an agent that exhibits reactive (in question 1), or state-based (in question 2), soccer behaviour.

ASSIGNMENT #2

due date: Wednesday Nov 13th, 5pm.

problem #1: deductive reasoning agent: (7 marks) Create a RoboCup agent that uses either an expert system or a planner or a theorem prover or an AND-OR tree. You can use sample code from the AI textbook [4] (probably the easiest way) or use code from any other LEGITIMATE library (as long as you have permission and that you include a link to the place you took it from!). But you are NOT allowed to implement your own planner or theorem prover or... etc (as history indicates that nearly every such attempt in such short time has ended up in failure!). Note that the agent doesn't need to really play soccer; all it needs to do is exhibit the fact that it can take the input from the Soccer Server, use the reasoning algorithm, and do something meaningful. To show that your agent is indeed reasoning and not just reacting:

if you use a planner, the resulting plan to execute should involve at minimum 2 STRIPS operators;
if you use an expert system, the forward or backward chaining engine should chain at minimum 2 rules;
if you use a theorem prover, at least one proof should have a depth of at minimum 2 steps;
if you use an AND-OR tree, the solution contingency tree should have a depth of at minimum 2.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies among various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show (i.e., calculate!) how the introduction of evidence about the environment (i.e., P(X|A,e) vs P(X|A)) changes the choice of the action that the agent will make. (note that this means that your hand-crafted probabilities should be such that the choice of the agent does change with the introduction of evidence)

1 page max!

Bundle your code and documentation for Q1 and the answer to Q2 in a zip file and submit on Brightspace. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: Monday September 30th, 5pm, 2024.

1- Come up with a reactive soccer-playing agent for RoboCup, as per the definition of a reactive agent found in the Wooldridge book. Use Krislet as the starting point for your code. The agent function, i.e. the mapping between the environment state and the action, should be stored in an editable text file separate from the code. One should be able to modify the behavior of your agent by simply editing the text file and without recompiling your code. In a short guide (about half a page and up to a page) tell us how to read, edit and make sense of your agent function definition, give a brief intelligible description of the function, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code.

2- Now come up with a state-based soccer-playing agent. Ideally, the behaviour of the agent (i.e., the Mealy machine) should again be stored in an editable text file separate from the code, but we're also ok with a hard-coded state machine as long as it is easy to modify it. Again, in a short guide (up to a page or two this time) tell us how to read, edit and make sense of your agent function definition, provide a human-readable Mealy machine diagram (in the extended UML FSM format discussed in class) corresponding to your implementation, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code. In addition, the guide should PROVE, using runs derived manually from the state machine or from logs obtained from running the agent, that the behaviour is indeed state-based and not reactive.

For each part of the assignment, bundle your code and your guide in a separate zip file, just like the zip bundle we provided you that contains Krislet and the RoboCup server and monitor. So basically your code should go where the Krislet folder is. I should be able to run your code just like I run Krislet. Store your guide at the top level of the folder hierarchy. Submit your two zip files on Brightspace.

Do not exceed the page limits. Do not hand-draw diagrams. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

due date: Thursday Nov 9th, 5pm.

problem #1: deductive reasoning agent: (7 marks) Create a RoboCup agent that uses either an expert system or a planner or a theorem prover or an AND-OR tree. You can use sample code from the AI textbook [4] (probably the easiest way) or use code from any other LEGITIMATE library (as long as you have permission and that you include a link to the place you took it from!). Note that the agent doesn't need to really play soccer; all it needs to do is exhibit the fact that it can take the input from the Soccer Server, use the reasoning algorithm, and do something meaningful. To show that your agent is indeed reasoning and not just reacting:

if you use a planner, the resulting plan to execute should involve at minimum 2 STRIPS operators;
if you use an expert system, the forward or backward chaining engine should chain at minimum 2 rules;
if you use a theorem prover, at least one proof should have a depth of at minimum 2 steps;
if you use an AND-OR tree, the solution contingency tree should have a depth of at minimum 2.

As in assignment 1, give a one page description of your approach: the justification for your choice, the input you used, the output of the algorithm (showing that you addressed the "minimum 2" rule above), how to run your code, what is the code doing, etc. Ideally, get your program to output to the console what is happening during execution (tree being generated and followed, rule being executed, proof obtained, plan generated and followed, etc.): this should help you debug what's happening and helps me understand it better too. Only Java code is accepted. I should be able to run your code just like I run Krislet. Code that is hard to compile and/or run will lead to severe mark deduction.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies among various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show (i.e., calculate!) how the introduction of evidence about the environment (i.e., P(X|A) vs P(X|A,e)) changes the choice of the action that the agent will make. (note that this means that your hand-crafted probabilities should be such that the choice of the agent does change with the introduction of evidence)

1 page max!

Bundle your code and documentation for Q1 and the answer to Q2 in a zip file and submit on Brightspace. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: Tuesday October 3rd, 5pm, 2023.

1- Come up with a reactive soccer-playing agent for RoboCup, as per the definition of a reactive agent found in the Wooldridge book. Use Krislet as the starting point for your code. The agent function, i.e. the mapping between the environment state and the action, should be stored in an editable text file separate from the code. One should be able to modify the behavior of your agent by simply editing the text file and without recompiling your code. In a short guide (about half a page and up to a page) tell us how to read, edit and make sense of your agent function definition, give a brief intelligible description of the function, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code.

2- Now come up with a state-based soccer-playing agent. Ideally, the behaviour of the agent (i.e., the state machine) should again be stored in an editable text file separate from the code, but we're also ok with a hard-coded state machine as long as it is easy to modify it. Again, in a short guide (up to a page or two this time) tell us how to read, edit and make sense of your agent function definition, provide a human-readable finite state machine diagram (in the extended UML FSM format discussed in class) corresponding to your implementation, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code. In addition, the guide should PROVE, using runs derived manually from the state machine or from logs obtained from running the agent, that the behaviour is indeed state-based and not reactive.

Do not exceed the page limits. Do not hand-draw diagrams. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

due date: beginning of class on Tuesday November 8th, 2022.

problem #1: deductive reasoning agent: (7 marks) Create a RoboCup agent that uses either an expert system or a planner or a theorem prover or an AND-OR tree. You can use sample code from the AI textbook [4] (probably the easiest way) or use code from any other LEGITIMATE library (as long as you have permission and that you include a link to the place you took it from!). Note that the agent doesn't need to really play soccer; all it needs to do is exhibit the fact that it can take the input from the Soccer Server, use the reasoning algorithm, and do something meaningful. To show that your agent is indeed reasoning and not just reacting:

if you use a planner, the resulting plan to execute should involve at minimum 2 STRIPS operators;
if you use an expert system, the forward or backward chaining engine should chain at minimum 2 rules;
if you use a theorem prover, at least one proof should have a depth of at minimum 2 steps;
if you use an AND-OR tree, the solution contingency tree should have a depth of at minimum 2.

As in assignment 1, give a one page description of your approach: the justification for your choice, the input you used, the output of the algorithm (showing that you addressed the "minimum 2" rule above), how to run your code, what is the code doing, etc. Only Java code is accepted. I should be able to run your code just like I run Krislet. Code that is hard to compile and/or run will lead to severe mark deduction.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies among various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show (i.e., calculate!) how the introduction of evidence about the environment (i.e., P(X|A) vs P(X|A,e)) changes the choice of the action that the agent will make. (note that this means that your hand-crafted probabilities should be such that the choice of the agent does change with the introduction of evidence)

1 page max!

Bundle your code and documentation for Q1 and the answer to Q2 in a zip file and submit on Brightspace. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: Tuesday October 4th, 6pm, 2022.

1- Come up with a reactive soccer-playing agent for RoboCup, as per the definition of a reactive agent found in the Wooldridge book. Use Krislet as the starting point for your code. The agent function, i.e. the mapping between the environment state and the action, should be stored in an editable text file separate from the code. One should be able to modify the behavior of your agent by simply editing the text file and without recompiling your code. In a short guide (about half a page and up to a page) tell us how to read, edit and make sense of your agent function definition, give a brief intelligible description of the function, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code.

Do not exceed the page limits. Do not hand-draw diagrams. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

due date: beginning of class on Monday November 15th, 2021.

problem #1: deductive reasoning agent: (7 marks) Create a RoboCup agent that uses either an expert system or a planner or a theorem prover. You can use sample code from the AI textbook [4] (probably the easiest way), implement the algorithm yourself (but that is additional burden on you to implement the algorithms correctly!), or use code from any other place (as long as you have permission and that you include a link to the site you took it from!). Note that the agent doesn't need to really play soccer; all it needs to do is exhibit the fact that it can take the input from the Soccer Server, use the reasoning algorithm, and do something meaningful. To show that your agent is indeed reasoning and not just reacting:

if you use a planner, the resulting plan to execute should involve at least two STRIPS operators;
if you use an expert system, the forward or backward chaining engine should chain at least two rules;
if you use a theorem prover, at least one proof should have a depth of at least 2 steps.

As in assignment 1, give a one page description of your approach: the justification for your choice, the input you used, the output of the algorithm, how to run your code, what is the code doing, etc. Only Java code is accepted. I should be able to run your code just like I run Krislet. Code that is hard to compile and/or run will lead to severe mark deduction.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies among various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show (i.e., calculate!) how the introduction of evidence about the environment (i.e., P(X|A) vs P(X|A,e)) changes the choice of the action that the agent will make. (note that this means that your hand-crafted probabilities should be such that the choice of the agent does change with the introduction of evidence)

1 page max!

Bundle your code and documentation for Q1 and the answer to Q2 in a zip file and submit on Brightspace. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: Monday February 1st, 6pm, 2021.

1- Come up with a reactive soccer-playing agent for RoboCup, as per the definition of a reactive agent found in the Wooldridge book. Use Krislet as the starting point for your code. The agent function, i.e. the mapping between the environment state and the action, should be stored in an editable text file separate from the code. One should be able to modify the behavior of your agent by simply editing the text file and without recompiling your code. In a short guide (about half a page and up to a page) tell us how to read, edit and make sense of your agent function definition, give a brief intelligible description of the function, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code.

2- Now come up with a state-based soccer-playing agent. Ideally, the behaviour of the agent (i.e., the state machine) should again be stored in an editable text file separate from the code, but we're also ok with a hard-coded state machine as long as it is easy to modify it. Again, in a short guide (up to a page or two this time) tell us how to read, edit and make sense of your agent function definition, provide a human-readable finite state machine diagram (ideally in the extended UML FSM format discussed in class) corresponding to your implementation, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code. In addition, the guide should PROVE, using runs derived manually from the state machine or from logs obtained from running the agent, that the behaviour is indeed state-based and not reactive.

Do not exceed the page limits. Do not hand-draw diagrams. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

due date: beginning of class on Wednesday March 4th, 2020.

problem #1: AgentReasoning: (7 marks) Create a RoboCup agent that uses either an expert system or planning or an AND/OR tree. You can use sample code from the AI textbook [4] (probably the easiest way), implement the algorithm yourself, or use code from any other place (as long as you have permission and that you include a link to the site you took it from!). Note that the agent doesn't need to really play soccer; all it needs to do is exhibit the fact that it can take the input from the Soccer Server, use the reasoning algorithm, and do something meaningful. To prove that your agent is indeed reasoning and not just reacting:

if you use a planner, the resulting plan to execute should involve at least two STRIPS operators;
if you use an expert system, the forward or backward chaining engine should chain at least two rules;
if you use an AND/OR tree, the resulting tree should have a depth of at least 2 OR branches.

As in assignment 1, give a one page description of your approach: the justification for your choice, the input you used, the output of the algorithm, how to run your code, what is the code doing, etc. Submit your code on cuLearn or include the URL (shortened) of your code. Only Java code is accepted.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies among various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show (i.e., calculate!) how the introduction of evidence about the environment (i.e., P(X|a) vs P(X|a,E)) changes the choice of the action that the agent will make. (note that this means that your hand-crafted probabilities should be such that the choice of the agent does change with the introduction of evidence)

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: beginning of class on Wednesday February 5th, 2020.

1- Come up with a reactive soccer-playing agent for RoboCup, as per the definition of a reactive agent found in the Wooldridge book. You can use Krislet as the starting point for your code. The agent function, i.e. the mapping between the environment state and the action, should be stored in an editable text file separate from the code. One should be able to modify the behavior of your agent by simply editing the text file and without recompiling your code. In a short guide (about half a page and up to a page) tell us how to read, edit and make sense of your agent function definition, give a brief intelligible description of the function, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code.

2- Now come up with a state-based soccer-playing agent. Ideally, the behaviour of the agent (i.e., the state machine) should again be stored in an editable text file separate from the code, but we're also ok with a hard-coded state machine as long as it is easy to modify it. Again, in a short guide (up to a page or two this time) tell us how to read, edit and make sense of your agent function definition, provide a human-readable finite state machine diagram (ideally in the extended UML FSM format discussed in class) corresponding to your implementation, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code. In addition, the guide should PROVE, using runs derived manually from the state machine or from logs obtained from running the agent, that the behaviour is indeed state-based and not reactive.

If you have access to the course on cuLearn, you can use it to submit your code. If not, in both your short guides, provide a URL (a short one! please use a URL shortener such as bit.ly or goo.gl) to where one can download your code.

The assignment (other than the code) should be typed (don't draw diagrams with a pencil!) and should not exceed the page limits. Only hard copy submissions are accepted (i.e. do NOT just upload your answers to cuLearn! Print and bring to me!). Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

due date: beginning of class on Tuesday March 5th, 2019.

problem #1: AgentReasoning: (7 marks) Create a RoboCup agent that uses either an AND/OR tree, an expert system or planning. You can use sample code from the AI textbook [4] (probably the easiest way), implement the algorithm yourself, or use code from any other place (as long as you have permission and that you include a link to the site you took it from!). Note that the agent doesn't need to really play soccer; all it needs to do is exhibit the fact that it can take the input from the Soccer Server, use the reasoning algorithm, and do something meaningful. To prove that your agent is indeed reasoning and not just reacting:

if you use an AND/OR tree, the resulting tree should have a depth of at least 2 OR branches;
if you use a planner, the resulting plan to execute should involve at least two STRIPS operators;
if you use an expert system, the forward or backward chaining engine should chain at least two rules.

As in assignment 1, give a one page description of your approach: the justification for your choice, the input you used, the output of the algorithm, how to run your code, what is the code doing, etc. Submit your code on cuLearn or include the URL (shortened) of your code. Only Java code is accepted.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies among various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show (i.e., calculate!) how the introduction of evidence about the environment (i.e., P(X|a) vs P(X|a,E)) changes the choice of the action that the agent will make. (note that this means that your hand-crafted probabilities should be such that the choice of the agent does change with the introduction of evidence)

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: beginning of class on Tuesday January 29th, 2019.

2- Now come up with a state-based soccer-playing agent. Ideally, the behaviour of the agent (i.e., the state machine) should again be stored in an editable text file separate from the code, but we're also ok with a hard-coded state machine as long as it is easy to modify it (see for example the State Pattern). Again, in a short guide (up to a page or two this time) tell us how to read, edit and make sense of your agent function definition, provide a human-readable finite state machine diagram corresponding to your implementation, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code. In addition, the guide should PROVE, using runs derived manually from the state machine or from logs obtained from running the agent, that the behaviour is indeed state-based and not reactive.

If you have access to the course on cuLearn, you can use it submit your code. If not, in both your short guides, provide a URL (a short one! please use a URL shortener such as bit.ly or goo.gl) to where one can download your code.

All questions will be judged by the neatness, correctness, usability (the code should be very easy to run) and reusability (the behaviors should be easy to edit) of the description, code and approach.

The assignment should be typed and should not exceed the page limits. Only hard copy submissions are accepted (i.e. do NOT just upload your answers to cuLearn! Print and bring to me!). Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

due date: beginning of class on Thursday June 7th, 2018.

if you use an AND/OR tree, the resulting tree should have a depth of at least 2 OR branches;
if you use a planner, the resulting plan to execute should involve at least two STRIPS operators;
if you use an expert system, the forward or backward chaining engine should chain at least two rules.

As in assignment 1, give a one page description of your approach: the input you used, the output of the algorithm, how to run your code, what is the code doing, etc. Include the URL of your code.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies among various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show (i.e., calculate!) how the introduction of evidence about the environment (i.e., P(X|a) vs P(X|a,E)) changes the choice of the action that the agent will make. (note that this means that your hand-crafted probabilities should be such that the choice of the agent does change with the introduction of evidence)

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

Here's the third problem that I considered posting but that you won't have to do:

problem #3: MachineLearning Come up with a hand-crafted AARF file representing a possible log of the behaviour of a soccer-playing agent (note: this doesn't have to be related to RoboCup at all). The non-categorical attributes/features could be anything in the environment that is potentially relevant to the agent's decision making (e.g., the position of particular objects), and the categorical attribute should be the agent's action. Now use the AARF in Weka to generate a decision tree. You should hand-craft your file in such a way that the resulting decision tree uses at least two decision branches. The file doesn't need to be long at all (no more than a page). In your submission, use one page to include the AARF file, and another page to describe what features and values you used in the AARF file, and to include the resulting decision tree.

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: beginning of class on Thursday May 24th, 2018.

2- Now come up with a state-based soccer-playing agent. Ideally, the behaviour of the agent (i.e., the state machine) should again be stored in an editable text file separate from the code, but we're also ok with a hard-coded state machine as long as it is easy to modify it (see for example the State Pattern). Again, in a short guide (up to a page or two this time) tell us how to read, edit and make sense of your agent function definition, provide a human-readable finite state machine diagram corresponding to your implementation, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code. In addition, the guide should PROVE, using runs derived manually from the state machine or from logs obtained from running the agent, that the behaviour is indeed state-based and not reactive.

In both your short guides, provide a URL (a short one!) to where one can download your code.

The assignment should be typed and should not exceed the page limits. Only hard copy submissions are accepted. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

due date: beginning of class on Tuesday June 6th.

problem #1: AgentReasoning (6 marks): Create a RoboCup agent that uses either an AND/OR tree, an expert system or planning. You can use sample code from the AI textbook [4] (probably the easiest way), implement the algorithm yourself, or use code from any other place (as long as you have permission and that you include a link to the site you took it from!). Note that the agent doesn't need to really play soccer; all it needs to do is exhibit the fact that it can take the input from the Soccer Server, use the reasoning algorithm, and do something meaningful. To prove that your agent is indeed reasoning and not just reacting:

if you use an AND/OR tree, the resulting tree should have a depth of at least 2 OR branches;
if you use a planner, the resulting plan to execute should involve at least two STRIPS operators;
if you use an expert system, the forward or backward chaining engine should chain at least two rules.

As in assignment 1, give a one page description of your approach: the input you used, the output of the algorithm, how to run your code, what is the code doing, etc. Include the URL of your code.

problem #2: MachineLearning (3 marks) Come up with a hand-crafted AARF file representing a possible log of the behaviour of a soccer-playing agent (note: this doesn't have to be related to RoboCup at all). The non-categorical attributes/features could be anything in the environment that is potentially relevant to the agent's decision making (e.g., the position of particular objects), and the categorical attribute should be the agent's action. Now use the AARF in Weka to generate a decision tree. You should hand-craft your file in such a way that the resulting decision tree uses at least two decision branches. The file doesn't need to be long at all (no more than a page). In your submission, use one page to include the AARF file, and another page to describe what features and values you used in the AARF file, and to include the resulting decision tree.

problem #3: agent in an uncertain environment: (3 marks) Now suppose that the soccer-playing agent has to choose between 2 or more actions, where the outcome of the actions on certain factors (those that determine the welfare of the agent) is uncertain.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies among various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show (i.e., calculate!) how the introduction of evidence about the environment (i.e., P(X|a) vs P(X|a,E)) changes the choice of the action that the agent will make. (note that this means that your hand-crafted probabilities should be such that the choice of the agent does change with the introduction of evidence)

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: beginning of class on Tuesday May 23rd, 2017.

2- Now come up with a state-based soccer-playing agent. Ideally, the behaviour of the agent (i.e., the state machine) should again be stored in an editable text file separate from the code, but we're also ok with a hard-coded state machine as long as it is easy to modify it (see for example the State Pattern). Again, in a short guide (up to a page or two this time) tell us how to read, edit and make sense of your agent function definition, provide a human-readable finite state machine diagram corresponding to your implementation, describe how your code executes the agent definition, how to run your code, and what kind of behavior to expect when running your code. In addition, the guide should PROVE, using runs derived manually from the state machine, that the behaviour is indeed state-based and not reactive.

In both your short guides, provide a URL to where one can download your code.

The assignment should be typed and should not exceed the page limits. Only hard copy submissions are accepted. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

Final hint: do not make things more complicated than they need to be. We don't expect an agent that plays well. We just want an agent that exhibits reactive (in question 1), or state-based (in question 2), behaviour.

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of how to design agents in various types of environments.

due date: beginning of class on Monday June 6th.

problem #1: AgentPlanning: We want to use a planning algorithm using STRIPS operators, based on the notations and example described in [2] and [3], to determine a course of action for a soccer-playing agent. Here we won't worry about the planning algorithm itself, but about setting up the description of the world and of the operators available to the agent.

Write down an example of a snapshot of an initial state description of the world in which the robot is.
Write down STRIPS-style definitions of the agents actions, therefore providing preconditions, deletions, and additions, as shown in [2].
Write down a feasible goal of this problem, and the sequence of subgoals to solve in order to achieve the initial problem, along with the intermediate models.

2 pages max!

problem #2: First Order Logic Read about Situation Calculus (for example in 10.4.2 of R&N) and use it to model the actions of a soccer-playing agent, and the effects those actions have on the environment in a few logical sentences. Try to make this agent as similar as possible to the one you came up with in problem#1.

1/2 a page max!

problem #3: agent in an uncertain environment: now suppose that the soccer-playing agent has to choose between 2 or more actions, where the outcome of the actions on certain factors (those that determine the welfare of the agent) is uncertain.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies amongst various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show how the introduction of evidence about the environment can change the choice of the action that the agent will make.

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: beginning of class on Wednesday May 25th, 2016.

Let's model the behaviour of a soccer-playing agent, using the PEAS methodology discussed in class (and discussed extensively in the Russell and Norvig textbook), as well as the agent-environment formalism also discussed in class and in the Wooldridge textbook. Whether this soccer game takes place in a real or virtual environment is not really relevant to this exercise; I'll leave it up to you to make it simple yet realistic enough to be recognizable as soccer.

define a limited set of actions available to the agent (remember, these actions should be relevant to playing soccer!)
define a discrete, non-deterministic soccer environment and your own state transformer function for that environment.
define: 1) a reactive agent; and 2) a state-based agent in this environment. Show a set of runs for your two agents, and how by examining the runs one can tell which agent is reactive and which one isn't.
Define an initial state of the environment that the agent starts in, and a goal for your agent in terms of a state (or multiple states) of the environment that the agent wants to reach. To make the exercise interesting, make it so that the agent cannot reach the goal right away with a single action. Define a sequence of actions for the agent that guarantees success (i.e. reaching the goal) for your agent, keeping in mind that the environment is non-deterministic.

All questions will be judged by the formality, NEATNESS (readability! use of graphics!), correctness, usefulness, and reusability of the modelling.

The assignment should be typed and SHOULD NOT EXCEED 4 PAGES. Page limits should be strictly respected (only the first 4 pages will be marked!!!). Choosing fonts that are too small in order to fit within the limits is NOT acceptable! Only hard copy submissions are accepted. Again, failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of how to design agents in various types of environments.

due date: beginning of class on Monday March 3rd.

Write down an example of a snapshot of an initial state description of the world in which the robot is.
Write down STRIPS-style definitions of the agents actions, therefore providing preconditions, deletions, and additions, as shown in [2].
Write down a feasible goal of this problem, and the sequence of subgoals to solve in order to achieve the initial problem, along with the intermediate models.

2 pages max!

1/2 a page max!

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies amongst various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show how the introduction of evidence about the environment can change the choice of the action that the agent will make.

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: beginning of class on Tuesday February 12th, 2014.

Let's model the behaviour of a soccer-playing agent. Whether this takes place in a real or virtual environment is not really relevant to this exercise; I'll leave it up to you to make it simple yet realistic enough to be recognizable as soccer.

define a limited set of actions available to the agent (remember, these actions should be relevant to playing soccer!)
define a discrete, non-deterministic soccer environment for the agent (that's the set "E") and your own state transformer function for that environment.
define: 1) a reactive agent; and 2) a state-based agent in this environment. Show a set of runs for your two agents, and how by examining the runs one can tell which agent is reactive and which one isn't.
Define an initial state of the environment that the agent starts in, and a goal for your agent in terms of a state (or multiple states) of the environment that the agent wants to reach. To make the exercise interesting, make it so that the agent cannot reach the goal right away with a single action. Define a plan for the agent that guarantees success (i.e. reaching the goal) for your agent, keeping in mind that the environment is non-deterministic.

All questions will be judged by the formality, NEATNESS (readability! use of graphics!), correctness, usefulness, and reusability of the modelling.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of how to design agents in various types of environments.

due date: beginning of class on Tuesday March 5th.

Write down an example of a snapshot of an initial state description of the world in which the robot is.
Write down STRIPS-style definitions of the agents actions, therefore providing preconditions, deletions, and additions, as shown in [2].
Write down a feasible goal of this problem, and the sequence of subgoals to solve in order to achieve the initial problem, along with the intermediate models.

2 pages max!

1/2 a page max!

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies amongst various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show how the introduction of evidence about the environment can change the choice of the action that the agent will make.

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: beginning of class on Tuesday February 12th, 2012.

define a limited set of actions available to the agent (remember, these actions should be relevant to playing soccer!)
define a discrete, non-deterministic soccer environment for the agent (that's the set "E") and your own state transformer function for that environment.
define: 1) a reactive agent; and 2) a state-based agent in this environment. Show a set of runs for your two agents, and how by examining the runs one can tell which agent is reactive and which one isn't.
Define an initial state of the environment that the agent starts in, and a goal for your agent in terms of a state (or multiple states) of the environment that the agent wants to reach. To make the exercise interesting, make it so that the agent cannot reach the goal right away with a single action. Define a plan for the agent that guarantees success (i.e. reaching the goal) for your agent, keeping in mind that the environment is non-deterministic.

All questions will be judged by the formality, NEATNESS (readability! use of graphics!), correctness, usefulness, and reusability of the modelling.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of how to design agents in various types of environments.

due date: beginning of class on Tuesday Feb 28th.

Write down an example of a snapshot of an initial state description of the world in which the robot is.
Write down STRIPS-style definitions of the agents actions, therefore providing preconditions, deletions, and additions, as shown in [2].
Write down a feasible goal of this problem, and the sequence of subgoals to solve in order to achieve the initial problem, along with the intermediate models.

2 pages max!

problem #2: expert systems: come up with a set of expert system rules used by a soccer agent to update its set of beliefs. Show, with an example, how receiving an update from the environment leads to inferring new beliefs by triggering rules via forward chaining.

1 page max!

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies amongst various factors as well as between actions and those factors relevant to the "well-being" of the agent.
Using the utilities attached to those "well-being" factors, show how the introduction of evidence about the environment can change the choice of the action that the agent will make.

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of general agent architectures.

due date: beginning of class on Tuesday February 7th, 2012.

define a limited set of actions available to the agent (remember, these actions should be relevant to playing soccer!)
define a discrete, non-deterministic soccer environment for the agent (that's the set "E") and your own state transformer function for that environment.
define: 1) a reactive agent; and 2) a state-based agent in this environment. Show a set of runs for your two agents, and how by examining the runs one can tell which agent is reactive and which one isn't.
Define an initial state of the environment that the agent starts in, and a goal for your agent in terms of a state (or multiple states) of the environment that the agent wants to reach. To make the exercise interesting, make it so that the agent cannot reach the goal right away with a single action. Define a plan for the agent that guarantees success (i.e. reaching the goal) for your agent, keeping in mind that the environment is non-deterministic.

All questions will be judged by the formality, NEATNESS (readability! use of graphics!), correctness, usefulness, and reusability of the modelling.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of AgentReasoning and AgentAdaptability.

due date: beginning of class on Monday November 15th, 2010.

Write down an example of a snapshot of an initial state description of the world in which the robot is.
Write down STRIPS-style definitions of the agents actions, therefore providing preconditions, deletions, and additions, as shown in [2].
Write down a feasible goal of this problem, and the sequence of subgoals to solve in order to achieve the initial problem, along with the intermediate models.

2 pages max!

problem #2: MachineLearning: We want to use MachineLearning to imitate the behavior of a fellow soccer-playing agent. To do this we would record its behavior (dash, turn, and kick actions) in various situations (as described by the combination of various non-categorical attributes) in a log file. Come up with a set of learning samples corresponding to such a log file, then feed the samples to Weka and generate a resulting decision tree. One page should the describe the categorical and non-categorical attributes of the problem, and list the samples in a table (10-20 rows), and another page should display the tree output by Weka. The tree should have *at least 3 branching points*.

problem #3: agent in an uncertain or partially inaccessible environment: now suppose that the soccer-playing agent has to choose between 2 or more actions which chances of success depend on certain aspects of the environment.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Decision Network (see R & N 16.5) describing probabilistic dependencies amongst various factors as well as between those factors and the chances of success of the actions.
Exploit your resulting model to show, numerically, how introducing new evidence modifies the probability of success of the actions.
Associate utilities to the consequences of each action, and combine them with the result from step 2 to show how the introduction of evidence about the environment can change the choice of the action that the agent will make.

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this assignment will evaluate your understanding of the general agent architecture, adversarial search and the application of propositional logic to building deductive agents.

due date: beginning of class on Wednesday October 20th, 2010.

question #1: general agent architecture, environments, states, state transformer functions

We want to build an agent that can determine, through a set of tests, which operating system (OS) is running on a given remote computer. We assume that there is a finite number of possible OSs, and that applying a given test on a given machine tells us which OSs are still possible candidates for that machine (the test can't rule them out) or not applicable anymore (the test can rule them out). Each test also has a cost associated with it (in terms of time or money).
Our goal is to build a system that can come up, with minimum cost, with a set of tests to answer the following question: what is the OS running on the machine?
First, formulate the problem the agent has to solve: what are the agent's environment, internal states, actions, the environment's state transformer function (or, as R&N calls it, the "transition model"), goal(s)/utility? Is the environment discrete/continuous, deterministic/non deterministic, accessible/partially accessible? Is it always possible to reach your goal? Do this as formally as possible.
Second, come up with a toy example of a particular run of your agent to illustrate, preferably graphically, your formalization above.
1 page max!
Note: you are NOT asked to solve the problem, but just to formulate and illustrate it. Also, you are not expected to be an expert in Operating Systems, just make up whatever tests look realistic to you.

question #2: adversarial search

We want to come up with an agent that can play the following two-player game successfully: there is an even number of boxes lined up next to one another, each containing a certain amount of money in it. The amount in each box is known to both players. Players take turns choosing a box and retrieving all the money from it, but they can only choose between one of the two boxes that are at either end of the line-up (i.e. choose between the leftmost box and the rightmost box). Once a box is chosen, it is removed from the game. The winner is the player who has retrieved the most money in total.

Example:

In the first round of the game, the player can choose 75 or 5. The number of boxes is then reduced to five. The second player then chooses the remaining leftmost or rightmost box, and so on.

Apply minimax search to this game (what is the utility, what are the states?) : illustrate it by showing the minimax tree in the case of 4 boxes to begin the game, with amounts of your own choosing.
In your example, is there a winning strategy? If so, what is it?
bonus question: Is there a general winning strategy, regardless of the number of boxes and their amounts?
2 pages max! (although 1 page should be sufficient!)

question #3: research question:

read section 7.7 of the Russell & Norvig (only in edition 3 unfortunately. It is entitled Agents Based on Propositional Logic. You will probably also need to read about the Wumpus World in section 7.2 to understand the example)
apply it to (partially) describe a deductive agent that can play at least one very small aspect of the game of soccer:
- describe a small part of the agent's knowledge base, percepts, actions, fluents, etc. in propositional logic;
- use the above to show one particular deduction upon reception of a new percept, using a short but complete proof;
- 1 page max!

All questions will be judged by the quality (formality, correctness, usefulness, reusability...) of the modelling, its description, and its exploitation.

The assignment should be typed. Page limits should be strictly respected (grades WILL be lost otherwise!). Choosing fonts that are too small in order to fit within the limits is not acceptable! Only hard copy submissions are accepted. Again, failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of AgentReasoning and AgentAdaptability.

due date: beginning of class on Wednesday November 4th, 2009.

In this assignment we will focus on different approaches for modelling the behavior soccer-playing agent and exploiting the resulting.

Write down an example of a snapshot of an initial state description of the world in which the robot is.
Write down STRIPS-style definitions of the agents actions, therefore providing preconditions, deletions, and additions, as shown in [2].
Write down a feasible goal of this problem, and the sequence of subgoals to solve in order to achieve the initial problem, along with the intermediate models.

2 pages max!

Come up with a simple yet realistic (in terms of dependencies and probability figures) Bayesian Network describing probabilistic dependencies amongst various factors as well as between those factors and the chances of success of the actions.
Exploit your resulting model to show, numerically, how introducing new evidence modifies the probability of success of the actions.
Associate utilities to the success of each action, and combine them with the result from step 2 to show how the introduction of evidence about the environment can change the choice of the action that the agent will make.

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this first assignment will get you to model and design simple agents and evaluate your understanding of AgentKnowledgeRepresentation.

due date: beginning of class on Wednesday October 14th, 2008.

question #1: state-based agent:

describe a simple state-based agent that can play at least some aspect of the game of soccer. To do so, you will have to first define the stimulii that the agent receives from the environment and the actions that it can use. Then provide a state machine that CORRECTLY and COMPLETELY captures the behavior of the agent.
the state machine should be designed such that it cannot be emulated by a reactive agent. Use selected runs of the agent that show that it is indeed not the case. Discuss your choices and the benefits and limitations of using a state-based architecture.
2 pages max!

question #2: deductive agent: describe, using propositional logic, a simple deductive agent that can play at least some aspect of the game of soccer. You will need to describe the various goals that the agent might attempt to achieve, the logical sentences that define the environment and capabilities of the agent, and a representation of the perception of the agent in terms of premises that can be added to the knowledge base. Show, with a proof using those logical sentences, how at least one of the goals can be achieved. 2 pages max!

question #3: research question: read up on Situation Calculus (there is a good section in the Russell & Norvig, or you can use Wikipedia as a starting point) and apply it to (partially) describe a deductive agent that can play at least one aspect of the game of soccer. 1 page max!

All questions will be judged by the quality (formality, correctness, usefulness, reusability...) of the modelling, its description, and its exploitation.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of AgentReasoning. You are asked to look at the problem of Operating Systems Discovery (OSD)using the techniques discussed in class. The goal of OSD is to guess what operating system is running on a given machine, using the way the machine reacts to various tests. Since you are not expected to know what kind of tests are typically used for OSD, you are free to imagine any kind of test that you think makes sense. You will not be judged on the pertinence of the tests.

due date: beginning of class on Tuesday October 28th, 2008.

problem #1: ExpertSystems: Use ForwardChaining as a way to determine the OS of a machine. In one page max, define some expert rules and show how they would trigger in a forward-chaining fashion to derive new facts based on some new input from the environment. Your answer will be judged based on the correctness of the inference, and the usefulness of the derived facts for the purpose of determining the OS of a machine.

problem #2: CompleteSearch or IncompleteSearch?: here we want to determine the complexity of OSD, which will help us decide between a CompleteSearch or IncompleteSearch approach.

One can consider the initial state of the problem to consist of the set of possible OSes running on that machine (the initial hypothesis). A test is then an action that, upon application to that state, can refine the hypothesis by outputting a new subset of that initial set. The exact outcome of a test is not known beforehand (otherwise why test?) but what is known is the set of different outcomes of the test: the actual outcome will depend on the actual OS that is being determined. The goal is to find the shortest sequence of tests that can help determine the OS.

Your task is to propose the idea of an algorithm which would determine such a sequence of tests, and to therefore show which of CompleteSearch or IncompleteSearch makes sense.

2 pages max!

problem #3: BayesianNetworks: One can also consider OSD as a process of reasoning with uncertainty. Come up with a simple (yet complete!) Bayesian Network capturing, for example, the influence of prior probabilities of each OS, the influence of response time or probability of a certain behavior in response to a test, and show how you can compute hte most probable OS when some of the evidence is uncovered.

1 page max!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this first assignment will get you to model and design simple agents and evaluate your understanding of AgentKnowledgeRepresentation.

due date: beginning of class on Thursday October 9th, 2008.

question #1: state-based agent:

describe a simple state-based agent that can play the game of soccer. To do so, you will have to first define the stimulii that the agent receives from the environment and the actions that it can use. Then provide a state machine that CORRECTLY and COMPLETELY captures the behavior of the agent.
the state machine should be designed such that it cannot be emulated by a reactive agent. Use selected runs of the agent that show that it is indeed not the case. Discuss your choices and the benefits and limitations of using a state-based architecture.
2 pages max!

question #2: deductive agent: describe a deductive agent that can play the game of soccer. You will need to describe the various goals that the agent might attempt to achieve, the logical sentences that define the environment and capabilities of the agent, and a representation of the perception of the agent in terms of premises that can be added to the knowledge base. Show, with a proof using those logical sentences, how the achievability of at least one of the goals can be deduced. 2 pages max!

All questions will be judged by the quality (formality, correctness, usefulness, reusability...) of the modelling, its description, and its exploitation.

The assignment should be typed. Page limits should be strictly respected. Choosing fonts that are too small in order to fit within the limits is not acceptable! Only hard copy submissions are accepted. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of AgentReasoning and AgentAdaptability.

due date: beginning of class on Tuesday February 26th, 2008.

problem #1: ExpertSystems: Use ForwardChaining as a way to update a soccer-playing agent's knowledge of the world given new input received from the environment. Such stimulus could be very "low-level", and the goal of forward-chaining would be to derive new facts that are more "high-level" and therefore more exploitable by the reasoning module of the agent.

In one page max, define some expert rules and show how they would trigger in a foward-chaining fashion to derive new facts based on some new input from the environment. Your answer will be judged based on the correctness of the inference, and the usefulness of the derived facts for the purpose of programming a soccer-playing agent.

problem #2: AgentPlanning: Our goal is to use a planning algorithm using STRIPS operators, based on the notations and example described in [2] and [3], to determine a course of action for a soccer-playing agent.

Write down an initial state description using the facts that you inferred in problem #1.
Write down STRIPS-style definitions of the agents actions, therefore providing preconditions, deletions, and additions, as shown in [2].
Write down a feasible goal of this problem, and the sequence of subgoals to solve in order to achieve the initial problem.

2 pages max!

problem #3: MachineLearning: We want to use MachineLearning to imitate the behavior of a fellow soccer-playing agent. To do this we have recorded its behavior (dash, turn, and kick actions) in various situations in a log file. Come up with a set of learning samples corresponding to such a log file (you can use ideas from the model you have used so far, in this assignment or the previous one), then feed the samples to Weka and generate a resulting decision tree. One page should the describe the categorical and non-categorical attributes of the problem, and list the samples in a table (10-20 rows), and another page should display the tree output by Weka. The tree should have at least 3 branching points.

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this first assignment will get you to model and design simple agents and evaluate your understanding of AgentKnowledgeRepresentation.

due date: beginning of class on Tuesday February 5th, 2008.

question #1: state-based agent: describe a simple state-based agent that can play the game of soccer. To do so, you will have to first define the stimulii that the agent receives from the environment and the actions that it can use. Then provide a state machine that CORRECTLY and COMPLETELY captures the behavior of the agent. Discuss your choices and the benefits and limitations of using a state-based architecture. 1 page max!

question #3: agent in an uncertain or partially inaccessible environment: now suppose that the soccer-playing agent has to choose between 2 or more actions which chances of success depend on certain aspects of the environment.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Bayesian Network describing probabilistic dependencies amongst various factors as well as between those factors and the chances of success of the actions.
Exploit your resulting model to show, numerically, how introducing new evidence modifies the probability of success of the actions and changes the choice of the action that the agent will make.

1 page max!

All questions will be judged by the quality (formality, correctness, usefulness, reusability...) of the modelling, its description, and its exploitation.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of AgentReasoning and AgentAdaptability.

due date: beginning of class on Tuesday November 7th, 2006.

problem #1: SearchMethods: We want to build an agent for RoboCup which plays by imitating another RoboCup agent, based on the log of its execution in past games.

The log is essentially a long list of scenes, where a scene is defined by:
- a set of objects visible to the player at that time, each defined by the type of the object: (ball, goal, teammate, opponent), its position with respect to the player, its direction and velocity;
- and the action taken by the player being imitated: one of turn, dash or kick.
The �brain� of the agent is an infinite loop that waits for an input from the RoboCup server, tries to match that input with the �closest� scene in the log using some distance calculation algorithm, and triggers the action of that scene.

Define a realistic distance calculation algorithm for this �brain�. The main difficulty is when there are more than one teammates or opponents in the current input, and they need to be paired with their closest counterparts in another scene. Give as many examples as needed to clarify your solution. Two pages max allowed!

problem #2: Planning (as seen in ExpertSystems): (adapted from Russell & Norvig) There is a monkey in a room with some bananas hanging from the ceiling, but a box is available that will enable the monkey to reach the bananas if he climbs on it. Initially, the monkey is at A, the bananas at B, and the box at C. The monkey and box have height "Low", but if the monkey climbs onto the box he will have height "High", the same as the bananas. The actions available to the monkey include "Go" from one place to another, "Push" an object from one place to another, "Climb" onto an object. Grasping results in holding the object if the monkey and object are in the same place at the same height.

Our goal is to use a STRIPS-type planning algorithm, based on the notations and example described in [2] and [3].

Write down the initial state description using the notation described in [3] (simple predicate logic)
Write down STRIPS-style definitions of the four actions, therefore providing preconditions, deletions, and additions, as shown in [2].
Obviously, the monkey wants to have the bananas. Write down the goal of this problem, and the sequence of subgoals to solve in order to achieve the initial problem.

2 pages max!

problem #3: MachineLearning: Come up with a set of learning samples describing the problem of intrusion detection (you can use ideas from the model you used in your previous assignment), then feed the samples to Weka and generate a resulting decision tree. One page should the describe the categorical and non-categorical attributes of the problem, and list the samples in a table (10-20 rows), and another page should display the tree output by Weka. The tree should have at least 3 branching points.

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this first assignment will evaluate your understanding of AgentKnowledgeRepresentation.

due date: beginning of class on Tuesday October 3rd, 2006.

question #1: first order logic: use FOL to describe a suitable aspect of the game of soccer in a few sentences (no more than 10!) in logic. Use those premises, as well as the axioms and production rules of first order logic (as seen in class) to derive a new sentence that is potentially useful and non-obvious.

question #2: BayesianNetworks: Various factors can be taken into account in determining whether an intrusion in a computer network has occurred or is about to occur: the time of day, the host�s operating system, the presence of a spike in incoming traffic, the nature of the incoming packets as well as their relevance to the services offered by the host. There are obviously many other factors; feel free to choose any factor(s) you want as long as it is realistic and relevant! This is not to test your knowledge in intrusion detection: just demonstrate your understanding of BayesianNetworks! You can use very limited discrete ranges for your factors if needed.

Come up with a simple yet realistic (in terms of dependencies and probability figures) Bayesian Network describing probabilistic dependencies amongst various factors as well as between those factors and the probability of occurrence of an intrusion.
Exploit your resulting model to show, numerically, how introducing new evidence modifies the probability of the occurrence of an intrusion.

question #3: PetriNets Find an article from a journal, conference or workshop, which uses petri-nets to model a particular aspect of agent-based systems. Describe, in one page, what problem the paper tackled, why was the petri-net model chosen, an example illustrating that choice (include a Petri-net diagram!), and some relevant explanation. Conclude with some personal comments on the article. Don't forget to provide the full reference to the paper!

Use one page per question!

Questions #1 and #2 will be judged by the quality (formality, correctness, usefulness, ...) of the modelling, its description, and its exploitation. Question #3 will be judged by the quality and pertinence of the writing, and how much one can learn about the article by reading your text.

The assignment should be typed. Only hard copy submissions are accepted. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of AgentReasoning and AgentAdaptability.

due date: beginning of class on Tuesday November 8th, 2005.

problem #1: SearchMethods: We want to build an agent for RoboCup which plays by imitating another RoboCup agent, based on the log of its execution in past games.

The log is essentially a long list of scenes, where a scene is defined by:
- a set of objects visible to the player at that time, each defined by the type of the object: (ball, goal, teammate, opponent), its position with respect to the player, its direction and velocity;
- and the action taken by the player being imitated: one of turn, dash or kick.
The �brain� of the agent is an infinite loop that waits for an input from the RoboCup server, tries to match that input with the �closest� scene in the log using some distance calculation algorithm, and triggers the action of that scene.

problem #2: BayesianNetworks: provide a complete description of a bayesian network (no more than 6 nodes) to describe a suitable aspect of the game of soccer. Use the resulting model to calculate an answer to a potentially useful and non-obvious question. One page max allowed!

problem #3: InterfaceAgents: we want to build an interface agent embedded in a Web browser that learns to filter unwanted advertisements by observing the user. We assume, to simplify the problem, that all we need is the URL of the ad picture (which contains the host name, domain name, extension, directory and subdirectories, file name�). Describe your solution, give concrete examples and a trace of execution. Two pages max allowed!

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this first assignment will evaluate your understanding of AgentKnowledgeRepresentation.

due date: beginning of class on Tuesday October 11th, 2005.

The goal of this assignment is to use 3 different models to represent very simply the different types of knowledge of a soccer player.

model #1: semantic web: use the Protege tool (and therefore RDF, RDFS and OWL) to describe a small subset of the ontology of the game of soccer in a graph of no more than 10 nodes. Provide the corresponding XML documents. Describe and use the properties of the relationships in your graph to answer a potentially useful and non-obvious query.

model #2: first order logic: use FOL to describe a very small part of the rules of the game of soccer in a few sentences (no more than 10!) in logic. Use the axioms and syntax rules of first order logic (as seen in class) to derive a new sentence that is potentially useful and non-obvious. Feel free to reuse elements of the ontology defined in model #1!

model #3: state-based agent: provide a state-machine to describe the behavior of a very simple soccer-playing agent (no more than 6 states). Make sure that each state provides some response to each valid input from ythe environment. You can of course reuse elements of the ontology defined in model #1, and you can also use the more expressive statechart notation if you feel the need to do so.

Use one page per model (you are allowed extra pages for the XML documents of model #1). Each model should not take more than half a page, the other half should be used to describe the model and (for models 1 and 2) show how the representation can be used by an agent to draw some useful inference.

This assignment will be judged by the quality (formality, correctness, usefulness, ...) of the modelling, its description, and its exploitation.

The assignment should be typed. Only hard copy submissions are accepted. Failure to comply strictly to the requirements will lead to a loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this assignment will evaluate your understanding of AgentReasoning and AgentAdaptability.

due date: beginning of class on Tuesday October 26th, 2004.

problem #1: SearchMethods: Resource allocation is one of the tasks that can be typically assigned to a software agent. Here is an example: a ski allocation agent has n pairs of skis available, to be assigned to n novice pupils. According to the tenets of the ski school, each pupil should receive a pair of skis matching his or her height. The agent's problem is to assign the n pairs of skis to the n pupils so as to minimize the sum of the absolute values of the differences between the height of a pupil and the length of the assigned pair of skis. What should the agent do and why?

Use one page max to analyze the problem and propose a solution that guarantees the best allocation, demonstrating why it does so.

problem #2: Planning: Describe the behavior of a very simple soccer player in terms of planning, following the STRIPS model covered in class (see [2] and [3]). You'll need to first define a set of operators, an initial model and a goal. Then apply STRIPS to show how the agent will come up with a sequence of actions in order to meet the initial goal. 2 pages max in total allowed for this problem!

problem #3: MachineLearning: Come up with a set of learning samples describing the problem of automatic email classification, then feed the samples to Weka and generate a resulting decision tree. One page should list the samples in a table (20 rows), and another page should display the tree output by Weka. The tree should have at least 3 branching points.

The assignment should be typed. Only hard copy submissions are accepted. Failure to follow any requirement will lead to loss of marks.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this first assignment will evaluate your understanding of AgentKnowledgeRepresentation.

due date: beginning of class on Tuesday October 5th, 2004.

The goal of this assignment is to use 3 different models to represent very simply the different types of knowledge of a soccer player: his behavior on the field, his knowledge of the soccer rules, his perception of the field, his tactics, his model of the other players, or any other aspect that can be modeled given the proposed representation languages.

model #1: propositional logic: use propositional logic to describe a suitable aspect of the game of soccer in a few sentences (no more than 10!) in logic. Use the axioms and syntax rules of propositional logic to derive a new sentence that is potentially useful and non-obvious.

model #2: semantic web: use RDF, RDFS and OWL to describe a suitable aspect of the game of soccer in a graph of no more than 10 nodes. Provide the corresponding XML documents. Describe and use the properties of the relationships in your graph to answer a potentially useful and non-obvious query.

model #3: bayesian networks: provide a complete description of a bayesian network (no more than 6 nodes) to describe a suitable aspect of the game of soccer. Use the resulting model to calculate an answer to a potentially useful and non-obvious question.

Use one page per model (you are allowed extra pages for the XML documents of model #2). Each model should not take more than half a page, the other half should be used to describe the model, justify the choice of the representation and show how the representation can be used by an agent to draw some useful inference.

This assignment will be judged by the quality (formality, correctness, usefulness, ...) of the modelling, its description, its exploitation, and the quality of the justification of the use of the given representations.

The assignment should be typed. Only hard copy submissions are accepted.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this first assignment will evaluate your understanding of AgentKnowledgeRepresentation.

due date: beginning of class on Thursday January 29th, 2004.

Use 3 different models to represent very simply the different types of knowledge of a soccer player: his behavior on the field, his knowledge of the soccer rules, his perception of the field, his tactics, his model of the other players, or any other aspect that you find interesting. Describe each model. Justify the choice of the representations.

Use one model per aspect. Use one page per model. The models need not be too detailed, for example 5-10 places + transitions for a petri net or 5-7 nodes for a bayesian net are reasonable. Each model should not take more than half a page, the other half should be used to describe the model, justify the choice of the representation and show how the representation can be used by an agent to draw some useful inference.
If you are not familiar with soccer, you do not need to describe very soccer-specific aspects, as long as you can justify that your model is still useful to an agent playing soccer.
You have no obligation to use the representations covered by the course. If you know any other representation that is adequate for your modelling task, feel free to use it, as long as you provide the description of the model itself and your justification for using it.

This assignment will be judged by the quality (correctness, usefulness, ...) of the modelling and its description, and the quality of the justification of the use of the given representations.

The assignment should be typed. Only hard copy submissions are accepted.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this second assignment will evaluate your understanding of AgentReasoning and AgentAdaptability.

due date: beginning of class on Friday Oct 25th, 2002.

Question 1: Search Methods: the goal of the n-queens problem is to place n queens on a n x n chessboard such that no queen attacks any other. A queen attacks any piece in the same row, column or diagonal. The figure below shows a solution to the 4-queen problem.

Describe how you could use a CompleteSearch technique to tackle this problem. Use a diagram to show a partial solution.

Question 2: Planning (as seen in ExpertSystems): (adapted from Russell & Norvig) There is a monkey in a room with some bananas hanging from the ceiling, but a box is available that will enable the monkey to reach the bananas if he climbs on it. Initially, the monkey is at A, the bananas at B, and the box at C. The monkey and box have height "Low", but if the monkey climbs onto the box he will have height "High", the same as the bananas. The actions available to the monkey include "Go" from one place to another, "Push" an object from one place to another, "Climb" onto an object. Grasping results in holding the object if the monkey and object are in the same place at the same height.

Our goal is to use a STRIPS-type planning algorithm, based on the notations and example described in [2] and [3].

Write down the initial state description using the notation described in [3] (simple predicate logic)
Write down STRIPS-style definitions of the four actions, therefore providing preconditions, deletions, and additions, as shown in [2].
Obviously, the monkey wants to have the bananas. Write down the goal of this problem, and the sequence of subgoals to solve in order to achieve the initial problem.

Question 3: MachineLearning: We want to come up with a software agent for Carleton University that determines which printer should be selected for a given printing job. All that the agent has at its disposal is a long history of past printing jobs, containing information such as type of user, type of document, distance between user and printer... and of course the name of the chosen printer. We will assume that there aren't many printers to select from (3 or 4 max).

Describe and justify which machine learning technique you would use to train the agent. Give a concrete example showing the input to the program, as well as its possible output (no need to actually run a program, although you are welcome to try!).

Words of advice:

Use one page (no more!) per question.
Do not give vague and general answers. You must apply your proposed technique to the problem at hand!
The assignment should be typed. Only hardcopy submissions are accepted.
The assignment will be judged by the correctness and completeness of the answer as well as the clarity of the explanation.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this first assignment will evaluate your understanding of AgentKnowledgeRepresentation.

due date: beginning of class on Tuesday Oct. 1st, 2002.

Use 3 different models to represent very simply the different types of knowledge of a baseball player: his behavior on the field, his knowledge of the baseball rules, his perception of the field, his tactics, his model of the other players, or any other aspect that you find interesting. Describe each model. Justify the choice of the representations.

Use one model per aspect. Use one page per model. The models need not be too detailed, for example 5-10 places + transitions for a petri net or 5-10 concept nodes for a semantic net are reasonable. Each model should not take more than half a page, the other half should be used to describe the model and justify the choice of the representation.
If you are not familiar with the game of baseball, feel free to choose any other collective sport.
You have no obligation to use the representations covered by the course. If you know any other representation that is adequate for your modelling task, feel free to use it, as long as you provide the description of the model itself and your justification for using it.

This assignment will be judged by the quality (correctness, usefulness, ...) of the modelling and its description, and the quality of the justification of the use of the given representations.

The assignment should be typed. Only hard copy submissions are accepted.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #2

topic: this second assignment will evaluate your understanding of AgentReasoning and AgentAdaptability.

due date: beginning of class on Thursday Feb 14th, 2002.

We want to come up with an agent that can play successfully a very simple version of the game of Nim. Here are the rules of this game: it consists of two players and a pile of sticks. Each player takes turns to remove one or two sticks from the pile. The player who is forced to take the last stick is the loser.

question 1: SearchMethods: first of all, give an evaluation of the complexity of the problem. Based on that, describe a complete or incomplete search solution to the problem.

question 2: ExpertSystems: you should probably play this game a few times and gain some expertise on it. Based on that, suggest a set of rules that you would use to program an expert system-based agent.

question 3: MachineLearning: describe a MachineLearning technique you would use to let the agent learn to play well.

Use one page (no more!) per question, even if your answer does not take the whole page.
Do not give vague and general answers: you should apply your technique to the game of Nim very explicitly and specifically. Use of figures and diagrams is strongly encouraged.
The assignment should be typed. Only hardcopy submissions are accepted.
The assignment will be judged by the 1- correctness, 2- completeness of the answer and 3- the clarity of the explanation, in that order.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

ASSIGNMENT #1

topic: this first assignment will evaluate your understanding of AgentKnowledgeRepresentation.

due date: beginning of class on Tuesday Jan. 29th, 2002.

Use one model per aspect. Use one page per model. The models need not be too detailed, for example 5-10 places + transitions for a petri net or 5-10 concept nodes for a semantic net are reasonable. Each model should not take more than half a page, the other half should be used to describe the model and justify the choice of the representation.
If you are not familiar with the game of soccer, feel free to choose any other collective sport.
You have no obligation to use the representations covered by the course. If you know any other representation that is adequate for your modelling task, feel free to use it, as long as you provide the description of the model itself and your justification for using it.

This assignment will be judged by the quality (correctness, usefulness, ...) of the modelling and its description, and the quality of the justification of the use of the given representations.

The assignment should be typed. Only hard copy submissions are accepted.

This exercise counts for 1/3 of the assignment portion (50%) of the overall grade.

Of course, all the problems are to be completed on your own!

due date:

Beginning of class on Thursday Oct. 26th, 2000.

second assignment: Reasoning

This assignment counts for 1/3 of the assignments' part (50%) of the overall grade. Just like the first assignment, use one page per question. The assignment must be typed. This is an individual work, and plagiarism will be dealt with "by the book". Use of diagrams and pseudo-code is strongly encouraged.

We will try in this assignment to study the game of tic-tac-toe and to come up with different AI approaches for a computer program to play against a human opponent. Here is a reminder of the rules of the game:

(borrowed from Yahooligans!) "This is a two player game, with one player being X and the other being O. X always goes first. The person playing X starts by marking one of the squares in the three by three grid with an X sign. The person playing O then marks another square with an O sign. Players take turns until one player wins i.e. has three in a row (either horizontally, vertically, or diagonally), or until all of the squares are filled."

X wins!

Question 1: Complete and incomplete search

First we will consider searching through the space of legal moves, in order to determine the best next move.

Before we proceed with any search, a couple of easy questions to warm up� How many possible game sequences are there anyway? How many different game states (including intermediate ones)? Do not worry about symmetries or unreachable states, we just want to have a rough estimate (the O notation can be used). Same questions for a n x n grid, i.e. a generalization of your previous answers.
It looks reasonable to proceed with a minimax search. Study and describe minimax search and how you would apply it to the game of tic-tac-toe. Be as specific as possible.
How would you make restrictions to the search if memory and CPU were very limited, or if you wanted to program an n x n version? Be as specific as possible.

Question 2: Expert rules

This time we are considering the use of expert rules to determine the next move. Describe backward chaining and how you would apply it to the game of tic-tac-toe, by providing some of the rules that you would implement and how they would trigger. No particular syntax is required, but �pseudo-Prolog� is preferred. Your program does not have to win all the time.

Question 3: Machine learning

Describe how you would apply machine learning to tic-tac-toe. Just choose one particular approach, describe it and apply it. Here is a list of possible approaches (but you don�t have to choose among those): genetic algorithms, reinforcement learning, inductive learning� Be as specific as possible when explaining your use of your chosen approach for the game of tic-tac-toe.

due date:

Beginning of class on Thursday Oct. 14th, 1999.

assignment: divided in 3 exercises:

knowledge representation:
- Use 3 different models to represent very simply the different types of knowledge of a soccer player: his behavior on the field, his knowledge of the soccer rules, his perception of the field, his tactics, his model of the other players, or any other aspect that you find interesting. Describe each model. Justify the choice of the representations.
- Use one model per aspect. Use one page max per model. The models need not be too detailed, for example 5-10 places + transitions for a petri net or 5-10 concept nodes for a semantic net are reasonable. Each model should not take more than half a page, the other half should be used to describe the model and justify the choice of the representation.
- If you are not familiar with the game of soccer, feel free to choose any other collective sport.
- You have no obligation to use the representations covered by the course. If you know any other representation that is adequate for your modelling task, feel free to use it, as long as you provide the justification.
reasoning:
- Resource allocation is one of the tasks that can be typically assigned to a software agent. Here is an example: a ski allocation agent has available n pairs of skis to be assigned to n novice pupils; according to the tenets of the ski school, each pupil should receive a pair of skis matching his or her height. The agent's problem is to assign the n pairs of skis to the n pupils so as to minimize the sum of the absolute values of the differences between the height of a pupil and the length of the assigned pair of skis. What should the agent do and why?
- Use one page max to analyze the problem and propose a solution.
article:
- give a summary of one of the articles found in the Bradshaw book, except the first introductory one.
- use one page max.

Each exercise counts for 1/3 of the assignment's overall grade.

Question 1 will be judged by the quality of the modelling and its description, and the quality of the justification of the use of the given representations.

Question 2 will be judged by the quality of the analysis of the problem, the quality of the solution, and the quality of the justification of the solution.

Question 3's evaluation will be based on the understanding of the paper, the expression skills, the difficulty of the chosen paper, and the quality of the critical analysis.

The assignment should be typed. Only hard copy submissions are accepted.

Of course, all the problems are to be completed on your own!

(last edited November 12, 2025)
Find Page by browsing or searching