Artificial Intelligence Programming Portfolio

 

Central Assignments Office (Middlesbrough Tower M2.08) Notes:

·        All work (including DVDs etc) needs to be secured in a plastic envelope or a folder and clearly marked with the student name, number and module title.

·        An Assignment Front Sheet should be fully completed before the work is submitted.

·        When Extenuating Circumstances (e.g. extension) has been granted, a fully completed and signed Extenuating Circumstances form must be submitted to the School Reception or emailed to scedt-assessments@tees.ac.uk.

Introduction

This ICA requires you to undertake the creation of three pieces of AI code using the Clojure programming language. It assesses all of the following learning outcomes and on successful completion of this module, the student will be able to:

 

Personal and Transferable Skills

1.  Communicate critical evaluations of complex programming concepts and solutions.

2.  Work collaboratively in small study teams to conduct research, develop software models and critically appraise the results obtained in the context of current research.

3.  Lead or participate in a small team to propose evidence-based decisions to a specified set of artificial intelligence problems.

4.  Select and apply appropriate problem solving methods, algorithms and language primitives appropriate for AI inference.

 

Research, Knowledge and Cognitive Skills

5.  Design, implement and evaluate inference engines for non-trivial problems.

6.  Build solutions to programming problems and critically appraise the results.

 

Professional Skills

7.  Autonomously adapt own approach in complex and unpredictable contexts.

 

Requirements

Students will develop a small portfolio of solutions to problems using concepts from functional and symbolic programming. The problems will address all learning outcomes. Students will work in small teams using established mechanisms for peer assessment which places responsibility on teams to critically appraise both the quality of team output and the contribution made by individuals within the team.

 

Student Responsibilities

You should attend and participate in all timetabled sessions for this module. These will predominantly take place in lab environments where you will undertake applicable and associated activities. You are expected to undertake additional practical worksheets that are disseminated periodically throughout the module.

You should undertake guided reading that will be recommended periodically to inform your personal study and research. It is essential you use this to inform your personal studies and activities.

You should submit all the necessary materials required for assessment of this module by the due dates given above.

There may be times when you need to seek advice or guidance on using the Library Services. This may include finding specific texts, literature searches, reading, note taking and/or academic report writing. Details can be found [here].

There may also be times when you need to seek additional Student Support to help you with other things surrounding your general studies. You can visit the Drop-In Centre, on campus in the Europa Building or online [here].

All of the above information is provided in order to support you with the necessary coursework and for you to get the most out of your studies.

 

Deliverables

Read these instructions carefully and follow them precisely. If you do not do so, you may lose (some or all) marks. You should attempt all three of the parts described below.

 

Part 1: Presentation problem

Choose one of the following problems and attempt all sub-parts for the chosen problem e.g. 1.1(a) and 1.1(b) for problem 1.1

 

Problem 1.1

(a)             Develop a function called bounds which takes a nested list of numbers as its only argument (i.e. a tree). Bounds should return the largest and smallest value in the tree. For example:

(bounds '(1 (-2 17 (4)) -8 (-6 13)))

==> (-8 17)

(b)                 As problem 1.1(a) but the tree may contain mixed values (not only numbers).

 

 

 

Problem 1.2

 

(a)             A function split takes a tree containing mixed data (symbols and numbers). Split returns a list of two structures, one containing all the symbols, the other containing all the numbers. NB: the ordering of data in the returned structure is not important.

(split '(1 (-2 dog 17 (4) cat) -8 (rat -6 13) mango))

==> {:nums (1 -2 17 4 -8 -6 13) :syms (dog cat rat mango)}

 

 

 

 

 

 

-- continued overleaf --

(b)            Similar to problem 1.2(a) but split now takes an argument which identifies how to split the data eg:

(split '(1 (-2 "string" dog [this is a vector] 17 (4) cat) -8 [and another vector] (rat -6 13) "blah" mango)

{:nums {:test number?}, :vects {:test vector?}

:syms {:test symbol?}})

==> {:nums {:test number?, :data (1 -2 17 4 -8 -6 13)}

:syms {:test symbol?, :data (dog cat rat mango)}

:vects {:test vector?,

:data ([this is a vector][and another vector])}

:other {:data ("string" "blah")}}

 

Problem 1.3

(a)             Write a function called nested-average, which takes a nested list of numbers as its only argument (i.e. a tree). The nested-average function should return the average of all numbers in the tree. For example

(nested-average ' (10 ((30 1) 20) (8 (5 (50 7)) 9) 40))

==> 18

(b)             Similar to 2.4 but the new function (called "stats") returns the smallest, largest, count and average profile of numbers in a tree. Values to be returned in a map.

(c)              As above but takes a sequence of comparators (like <, >=, or user defined) to determine which stats are returned.

 

 

 

-- continued overleaf --

Problem 1.4

(a)             Strict binary trees have two branches from each non-terminal node: a left branch and a right. We can conveniently represent binary trees using lists or vectors, for example:

can be represented as:

'[[[a b] c] [d [[e f] g]]]

Write a function maximum-tree-sum which takes a binary tree containing positive and negative numbers and returns the sum of numbers in the subtree which contains the largest of these sums. For example, with the tree below: the maximum-tree-sum is 10, summed from the blue subtree.

(b)             Extend problem 1.4 so it returns (i) the maximum tree-sum (ii) the minimum tree-sum

(iii) a sequence of all zero-sum subtrees.

Problem 1.5

(a) Strict binary trees have two branches from each non-terminal node: a left branch and a right branch. We can conveniently represent binary trees using lists or vectors, for

example:

 

 

...can be represented as:

'[[[a b] c] [d [[e f] g]]]

(a)             Write a function spin, which takes a binary tree as its argument and returns a tree formed by rotating each of the non-terminal nodes in the original tree. The tree above

 

would look like this...

(a)             Spin and palindrome: As problem 1.5 but also reports on any trees it finds which are palindromes.

(b)             Spin power-set: A spin-power-set (our term invented here) is a power-set of all trees where any of its subtrees may be spun/rotated or not. So:

[c [b a]], [[b a] c], [c [a b]], [[a b] c]

are all part of the same set but

[a, [b c]]

is not.

Write a function to return the spin-power-set of a tree.

 

Part 2: UVA problem

The UVA problem database is a collection of computing problems that can be coded using Clojure. The following links are to a selection of problems from that database, each link navigates to a PDF file of the problem specification. All problems are tree or graph related. Teams should choose one of the problems to solve

103 · 104 · 115 · 116 · 117 · 124 · 125 · 167 · 168 · 186 · 193

301 · 302 · 310 · 314 · 315 · 336 · 341 · 347 · 352 · 383

 

Part 3: Operators

You are required to build a small collection of state changing operators in the style used in lectures. Each operator will have preconditions, additions, deletions and a textual descriptor. You may invent new types of tuple as required by the problem you are given.

Problems are outlined below (see tutors for clarification if necessary). Your final collection of operators should work with the mops-search mechanism. You will be expected to demonstrate your operators using sample start and goal states. You should show the operation of mops-search with at least 3 start/goal combinations.

When designing your operators think about “what should be possible” not just what you will want them to do during a given test. Advanced solutions will also consider efficiency aspects of their operators. The problems specify some operators which you should build, you may also build others if this helps your solution.

 

An example operator

(def move-op

'{:txt [?agent moves from ?place1 to ?place2]

:pre ([isa ?agent agent] [at ?agent ?place1]

[next-to ?place1 ?place2])

:del ([at ?agent ?place1])

:add ([at ?agent ?place2])

})

Choose one of the problems from the following list:

 

Problem 3.1: Sliding doors

This scenario is concerned with doors. Doors can be in different states (open or closed, locked or unlocked). Doors connect rooms and are un/locked with specific keys.

Specify and build the following operators...

•         open (an unlocked door)

•         close (a door)

•         lock (a door with a key)

•         unlock (with a key)

•         move (from one room to another)

 

Problem 3.2: Lifting

This scenario is based around using a lift. Agents can “call” a lift by pressing the button outside the lift door in a corridor, on calling a lift there will be a short delay then the lift will arrive and the doors will open. Once entering the lift a floor can be selected (using a button inside the lift). After selecting a floor, the lift doors will close and it will start to move. After a short delay it will reach the chosen floor and the doors will open. You may assume that your operators control all agents using the lift.

Specify and build the following operators...

•         call-lift (from the corridor, assume that there is only one button per floor, not

•         separate buttons to request a lift going up and another going down)

•         select-floor (by pressing a button inside the lift)

•         enter-lift (from the corridor)

•         exit-lift (to the corridor)

•         wait (for a lift after it is called)

•         wait (for a lift to reach the selected floor)

 

Problem 3.3: Climbing

Some objects can be held by agents (grabbable objects), some can be platforms, and some can be climbed, some platforms can be climbed, and some climbable and/or platform objects are also ‘grabbable’.

A platform object can have other objects placed on top of it. Agents can pick/drop grabbable objects off/on a platform if they are standing on the platform.

Specify and build the following operators...

•         climb-on (a climbable object at roughly the same position as the agent)

•         climb-off (a climbable object)

•         pick-off (an object from a platform)

•         drop-on (an object on a platform)

NB: you must also be able to test your work using pick-up, drop and move (either as they were defined in lecture materials or with some modification).

 

 

Problem 3.4: Cranial loading

There is a small container terminal in Gliwice, Poland where containers are loaded/unloaded to/from boats. In 2010/11 researchers were investigating using STRIPS operators to automate this process. That much is true, the rest of this is fiction...

Boats arrive at one side of the terminal (one at a time), trains arrive at the other side. Boats and trains both have a line of places/platforms/locations where containers can be stacked.

The line of platforms on a boat/train are described with tuples like...

[platforms train-1 (t1 t2 t3 t4 t5 t6)]

A crane is positioned between the boat arrival side and the train arrival side. The crane can rotate but cannot move forward/backward along the terminal. Boats and trains can move, when train-1 is positioned to load/unload to/from platform p3, this will be represented by the tuple...

[position train-1 t3]

Boats and trains can move forwards and backwards (your operators should handle this but they do not need to deal with boats/trains moving off the terminal – this is managed by other operators).

Containers are stacked platform positions (for the sake of this exercise you can assume that there is no limit to the height of stacks). When the crane lifts a container it removes it from the top of a stack, when it places a container, it puts it on the top of a stack. Stacks are represented by the following type of tuple...

[stack t3 (a b c)]

...where a, b and c are containers (a is on the top of the stack).

 

Specify and build the following operators...

•         lift-container          picks up a container from the top of the current stack

•         place-container     puts a container onto the current stack

•         rotate-crane           switch the crane from the boat side to the train side and vice-versa

•         shunt-fwd               move a boat/train forward one platform/position (do nothing if this already at the last position in the sequence)

•         shunt-back             move a boat/train backward one platform/position (do nothing if this already at the last position in the sequence)

 

 

Problem 3.4: Robot cars

In this example robot cars move stock materials around a small warehouse.

The warehouse is split into zones with one car in each zone. Cars cannot move between zones but it is possible to move stock from one zone to another because zones connect to each other by Exchanges – shared areas where one car can leave stock for another (note there is only room for one piece of stock in an exchange).

Each zone is laid out in a grid formation where Corridors run north-south or east-west and connect to each other at Junctions. The corridors are full of Bays – the bays are where stock is stored. So far so good but there is a small complication... the stock is mostly (you can assume always) longer than the width of the corridors so they can only be carried along the corridors if they correctly aligned this means that cars sometimes need to rotate stock at corridor junctions.

Specify and build operators to achieve the following...

•         collect-stock           from the car's current bay/exchange (cars must already have travelled to the correct bay), note that cars can only hold one stock item at a

time (you may split this into 2 operators if you wish)

•         deposit-stock         put the stock at the bay/exchange where the car is (you may split into 2 operators if you wish)

•         move-to-bay           move a car to a bay in its current corridor

•         move-to-junction move a car to a junction/exchange from its current corridor (you may combine this with other move operators if you wish)

•         rotate-car                rotate a car (and its stock) this can only happen at a junction

You will also need to specify world knowledge (static/unchanging tuples) to capture details about which junctions connect to which corridors, where the bays are and the location of exchanges.

NB: ensure your definitions describe a world large enough to test but do not make it larger than necessary. If necessary you can write small helper functions to generate tuples from other data types.

 

Peer marks

•         Groups will distribute 13 peer assessment points for each ICA part, individual marks will be calculated from the group mark and peer assessment points as explained under the

relevant section at DigMusic

•         An individual’s overall mark will be a combination of their marks from each of the ICA parts (marks from all papers will have the same weighting)

Marking and submission

•         Each part of the ICA will be marked during normal class time by a presentation made by the team to one or more members of staff.

•         Group marks and feedback for the code will be given after each presentation.

•         One member of each team should upload a ZIP file of the team's work to Blackboard on the same day as the presentation. The ZIP file should contain:

•         source code

•         any diagrams and/or supplementary text

•         peer marks for all team members (out of 13)

 

Marking/grading criteria

This ICA counts for 100% of the overall module grade. The following learning outcomes will be assessed:

 

Personal and Transferable Skills

1.  Communicate critical evaluations of complex programming concepts and solutions.

2.  Work collaboratively in small study teams to conduct research, develop software models and critically appraise the results obtained in the context of current research.

3.  Lead or participate in a small team to propose evidence-based decisions to a specified set of artificial intelligence problems.

4.  Select and apply appropriate problem solving methods, algorithms and language primitives appropriate for AI inference.

 

Research, Knowledge and Cognitive Skills

5.  Design, implement and evaluate inference engines for non-trivial problems.

6.  Build solutions to programming problems and critically appraise the results.

 

Professional Skills

7.  Autonomously adapt own approach in complex and unpredictable contexts.

 

 

 

Portfolios of code will be assessed according to:

•         The solutions to functional programming problems:

◦   Correctness of the solutions proposed

◦   Critique of the different possible solutions

◦   Appropriate and evidenced use of appropriate data structures

•         The construction of inference mechanisms:

◦   The design and implementation of inference engines

◦   Algorithm development

◦   The evaluation and critique of possible solutions

◦   An appraisal of the use of symbolic, functional and/or declarative programming

It should be noted that any marks offered are provisional until they have been confirmed by the relevant Course Assessment Board and in accordance with University Assessment Regulations.