Back to CS 4260/5260 main page.

Programming Project 4

Program 4 is relatively open ended and gives you considerable leeway in the specification of the project. In specifying the project you should scope it appropriately as an approximately two week project, remembering too that you can use AIs to assist in any and all of the steps of software development — specification, design, implementation, testing, documentation.

Deliverable 1: As a “first deliverable” for Program 4 you will be submitting a specification for what you intend, which we will briefly examine and approve. The format of this first deliverable will be an overview of what you intend and scoping guidelines that are consistent with a two week effort. This deliverable addresses items 1 and 2 of the issues addressed in a more comprehensive specification (which you aren’t addressing for this program). Identify the form and content of expected results. See the course schedule for the due date of the first deliverable.

Project Examples: Here are examples of some possible projects. You are free to build on these or to do something else, with the understanding that it must be integral to a road trip recommender system.

• Idea 1 Decision tree guidance. Modify the system so that it consults a decision tree to identify the preferences  corresponding to a user. You could learn the decision tree from artificial data that you create, but for purposes of this idea you could hand craft it. This idea would probably most directly build on Program 2, and perhaps program 3 as well.
• Idea 2 User control. Insert more user control into search. For example, allow the user to restrict the available locations/edges; allow setting a set of required locations that must be part of the road trip; allow the user to define a path already in a road trip and ask the system to generate a new path, presumably that is similar in some way (either thematically similar with a different set of locations or geographically similar but includes more preferred theme-sets). There are other ways to integrate user control into search that you can explore. This idea would probably most directly build on Program 2.
• Idea 3 Machine Learning of road trip sub-sequences (aka macro “operators”). Create artificial data that is intended to represent road trips by a large number of users, and extract popular sub-sequences from the data, which can then be used in future road trip recommendations. This idea might be coupled with the next idea, because simply learning and using popular macros does not necessarily improve search efficiency.
• Idea 4 Machine Learning of road trip policies. Create artificial data that is intended to represent road trips by a large number of users, and extract popular or rational next-step policies — that is, from a location with associated themes, use either of the two supervised machine learning approaches we studied to select the single next location from among the possible neighbors.
• Idea 5 Semantic web. Construct and use a semantic web (e.g., in the form of a set of triples that relate different themes/locations/concepts) to help guide the creation of road trips.
• Idea 6 Dynamic Preferences. In constructing a road trip, it may be that after adding a location with an attraction related to a theme (e.g., museum), a user’s preference for that theme with respect to subsequently selected locations may decrease (i.e., a user may not want too much of a good thing). Thus, theme preferences might change along a search path, and change differently along different search paths as search for complete road trips progresses.

Deliverable 2: Submit the following.

• Fully documented source code listing, or pointer to one that is accessible to Doug and Kyle, with a ReadMe file.
• A Powerpoint presentation (.pptx) that identifies developers and describes the program specification, design, implementation, and results. Include a slide with reflection on the development process, to include the use of any AI.
• A 5-10 minute video presentation using the slides immediately above.

See the course schedule for the due date of the second (and final) deliverable.

—————————— End of Program 4 specification ——————————–

Programming Project 3

Program 3 has you construct and test methods of machine learning on data about a user’s preferences for locations and for edges. Program 3 requires that we conceptually expand our treatment of utilities beyond a single real number per location and per edge. Rather, single real values for utilities are computed from themes (aka factors aka features), each of which is assumed to have a micro-utility in the mind of a user. For example, a user may really like civil rights history – one theme (or factor) — and the same user may not like amusement parks as much. So the user will prefer locations and edges that feature civil rights histories to locations and edges with only amusement park attractions. Of course, each location and edge can be associated with attractions covering many themes, and a location’s factored utility for a user is some function of the micro utilities of the user for the themes that characterize the location/edge attractions. The function to compute an overall factor utility (or location and edge preference) over theme utilities will be learned from data on locations, edges, attractions, and themes.

Background/Context: Here is some context that will help in your understanding of terms. Suppose you have a tool that is based on your task for Program 2 – to find and present round trip road trip suggestions to a user, perhaps augmented with a visual overview of the trip, as well as a summary of potential attractions at locations and on edges. Don’t worry about the details of the recommender interface for now, except suppose that it has a slider so that when a road trip is suggested the user can use the slider to give an overall real-valued utility for the suggested road trip from 0.0 to 1.0. This is only a pre-trip projection of course, but it can always be adusted later with a post-trip correction. The intent behind the interface’s design is to gather information about a user’s preferences while demanding relatively little of the user.

So what we have from this interaction with the round trip road trip recommender interface is a set of road trips, each associated with a single utility score between 0.0 and 1.0. We will assume that such data is all preprocessed into a dataset of themes and utility. You will be given a data set of the following form:

Data Set =

{ (U1 T11, T12, T13, …, T1m),

(U2 T21, T22, T23, …, T2m),

(U3 T31, T32, T33, …, T3m),

. . .

(Un Tn1, Tn2, Tn3, …, Tnm)}

Uk is the utility of the kth road trip , and Tkj is a count of the number of times that the theme Tj appears at a location and/or edge in the kth road trip. You need not worry about how the preprocessing occurs. because you are given the data as a csv file as formatted above, but you should read Section 12.1 of Poole and Mackworth (reading assignment for Week 9), and you should understand how the artificial data set on which you will test your learning algorithms was actually generated.

The data set itself is given here. It is formatted appropriate for supervised learning.

(a) In the case of learning decision trees, the utilities (the target or dependent variable) is divided into five discrete ranges, thus making performance a classification task. The 5 ranges are: ‘great’ is equivalent to [0.8, 1.0], ‘good’ is equivalent to [0.6, 0.8), ‘ok’ is equivalent to [0.4, 0.6), ‘low’ is equivalent to [0.2, 0.4), and ‘very low’ is equivalent to [0.0, 0.2). You will preprocess the data so that each Uk is replaced by one of the 5 labels from ‘great’ to. ‘very low’.

(b) In the case of learning with back-propagation, the utilities are kept as real valued, thus making performance a regression task. The dataset that you are given is suitable for training a back-propagation network with m input units and 1 output unit.

The independent variables are the same for (a) and (b).

Deliverables: You will implement

• decision tree learning using the top-down induction method, and
• backpropagation using artificial neural networks with at least one hidden layer, in addition to an input and output layer. Again, the input layer should have one input node for each input feature in your back propagation data design, and one output node for the real valued utility.

This implementation must supply fully documented source code. You are allowed to use AI tools to help implement and document the software, but you cannot use off the shelf library implementations of these systems. I want you to actively think through the code.

Evaluation of the systems will use 5-fold cross validation, measure prediction accuracy in the case of decision tree induction experiments and mean-square error in the case of back propagation. For decision tree experiments you will vary the maximum depth of decisions, looking at max depth of 2 (the root is at depth 0) and max depth 5. Revise the top-down induction of decision trees from lecture (and the text) so that the domain of variables and classes can vary rather than all being binary valued. For back propagation experiments you will vary the number of hidden units, looking at 4 hidden units and 8 hidden units, so unlike the definition here you should implement a version that allows you to vary the number of hidden units, and optionally you can parameterize the number of hidden layers too.

You will submit a report of approximately 5 pages that includes tables reporting the mean accuracies and variance (for DTs) over the 5 folds for each max depth, and mean MREs and variance (for back propagation) over the 5 folds for each hidden layer size.

The bare minimum that we would like to see in your report is

• An opening paragraph overview of what you’ve done (1. Introduction)
• A couple of paragraphs on experimental design (2. Experimental Design))
• The experimental results in table form as described in lecture, plus a brief narrative description, notably a summary of the differences between the two DT conditions (accuracy/variance differences between max depths of 2 and 5), and between the two backprop conditions of number of hidden units. (3. Experimental Results)
• Your hypotheses about why the  two conditions for each learning system vary between experimental conditions, informed by your knowledge of the respective learning methods. (4. Discussion of Results, part a)
• Your comments relating the DT results and the backprop results, remembering that the DT results are in terms of accuracy and backprop results are in terms of error (i.e., accuracy and errors are inverses), and that the DT results are categorization (finite, discrete, ordered classes) and backprop prediction is along a continuous dimension. Are the two sets of results comparable in any way? Analyses will potentially vary considerably across submissions. (4. Discussion of Results, part b)
• If you used AI to implement, evaluate, document the systems then 1 or more paragraphs of the experience and any insights on  strengths and weaknesses (5. General Discussion)
• 5. Concluding remarks

If this comes out to fewer than 5 pages, or more than 5 pages, 1.5 spacing, 1 inch margins, 12 pt  font, then that’s fine.

Additionally, some submissions might go beyond the specs, for example tests with different DT pruning strategies and different backprop activation functions. Such efforts are eligible for bonus points that will essentially be extra credit.

—————————— End of Program 3 specification ——————————–

Programming Project 2

Part a) Program 2 will expand on Program 1 (see that assignment below). Program 2 is concerned with performing utility-driven search. Instead of anytime A* search from a designated start location to a designated goal location, you will develop a program that searches for a round trip that begins and ends at a single designated location. This is to be an anytime search that returns alternative, different roundtrips, one at a time, until the user says to stop. Its desirable that a roundtrip road-trip should have high utility as measured by a utility function, but that the road trip must also take no more than a specified maximum amount of time.

To perform an anytime utility-driven, time-constrained search will require bases for computing utility and for estimating time.

1) You will create a local and team-specific copy of the locations and edges for Program 1.

2) You will augment each location and edge with its own preference value. For purposes of testing on Program 2 do the following.

a) Write a function called location_preference_assignments (a, b) that assigns random values between a=0 and b=1 inclusive using a uniform distribution to each location independently.

b) Write a function edge_preference_assignments (a, b) that assigns random values between a=0 and b=0.1 inclusive using a uniform distribution to each edge independently. Note that edges have a smaller preference upper bound than locations for Program 2.

3) Write a function total_preference (roadtrip) that returns the sum of all location and all edge preferences in a road trip. The roadtrip argument can be any graph of valid locations and edges – it need not be round trip, and it need not be connected. You decide on the internal representation of the roadtrip argument.

4) Write a function called time_estimate (roadtrip, x) that computes the time required by a road trip in terms of its constituent edges and locations as follows.

a) The time at a location is a function of the preference value, v_loc, assigned to the location – the greater the preference for a location, the more time spent at the location. Write a function time_at_location (v_loc) of your choice, under the constraint that if v_loc1 >= v_loc2, then t_loc1 >= t_loc2.

b) The base time required to traverse an edge is time t = d/x, where x is a specified speed in mph (e.g., x = 60), and d is the weight (distance in miles) of the edge. Note that x is assumed the same for all edges.

c) An additional amount of time on an edge is a function of the preference value, v_edge, assigned to it. In particular, the additional time spent on an edge is computed by add_time_on_edge (v_edge), which for Program 2 will simply be a call to time_at_location (v_edge).

d) time_estimate (roadtrip, x) returns the sum of times at all locations and on all edges of the road trip using x as the assumed travel speed on edges. The roadtrip argument can be any graph of valid locations and edges – it need not be round trip, and it need not be connected.

5) Write a top-level function

RoundTripRoadTrip (startLoc, LocFile, EdgeFile, maxTime, x_mph, resultFile)

that does an anytime search for round trip road trips.

• Total round trip road trip preference and time should not include preference and implied time of startLoc!
• Road trips that are returned cannot exceed maxTime (in hours) and the search should be designed such that round trips with higher total preference are more likely to be found earlier than later. That is, if time_estimate(RTRT_j, x_mph) <= maxTime and time_estimate(RTRT_k, x_mph) <= maxTime and total_preference (RTRT_j, x_mph) > total_preference (RTRT_k) then its desirable (though not required) that RTRT_j be returned before RTRT_k.
• Note that there is no requirement that a round trip road trip visit any location at most once, but you can add such a requirement (or preference), and document it, and in any case your time estimates should not double count visits to the same location on the same road trip for Program 2.

A Test Run

A solution will be written to the screen and the resultFile, using the same format for both cases. Each solution path is identified by a unique program-generated solutionLabel. The user will then be asked whether another solution should be returned. If ‘yes’, then the anytime search continues. These steps can occur indefinitely until the user answers ‘no’, or until there are no more candidate solutions, at which time the search terminates and returns a summary of its run, including

(a) the instrumented runtime of all continuations of the search (that is, do not include the time that search is paused between solutions so that you can answer yes/no).

This summary will be written to screen and to the resultFile immediately following the last solution returned for a given round trip.

Each solution path is essentially a sequence of edges that connect the start location back to the start location, with intermediate locations interLoc_i.

solutionLabel   startLoc  maxTime x_mph
1. startLoc   interLoc₁ edgeLabel  edgePreference  edgeTime  interLoc₁Pref  interLoc₁Time
2. interLoc₁ interLoc₂ edgeLabel  edgePreference  edgeTime  interLoc₂Pref  interLoc₂Time
…
N-1. interLoc_N-1 startLoc edgeLabel  edgePreference  edgeTime
startLoc  TotalTripPreference  TotalTripDistance  TotalTripTime

Each solution path is followed by a new blank line.

Each line, except the first and last, corresponds to an edge between two locations with those labels given first and second on the line, followed by the edgeLabel between them, the edge preference value, the edge time (base + additional), and the preference and time of the second of the locations on the line.

As in Program 1, while the data provides undirected edges each line of a solution gives a directed edge, in which the direction is from first location to the second location in the line of output. So your program will have to revise (or reinterpret) the undirected edges to be directed edges as appropriate. This shouldn’t be difficult.

Deliverables

You are to do at least three round trip test runs, where there will be a separate resultFile for each run. Between runs you will reinitialize location and edge preferences randomly as specified above, and recompute times accordingly.

You will be submitting (a) a fully documented program listing, (b) a summary and reflection on the use of AI in all aspects of the assignment, (c) resultFiles for at least 3 test runs (i.e., 3 anytime searches of at least three continuances each), d) a ReadMe file with comments on running your code and on your test runs (e.g., did any of your test cases correspond to situations in which no solution was possible? did your solutions monotonically decrease in value? did all test runs lead to solutions that met the hard time constraints? anything notable about runtime or search strategy?).

Part B) The Google doc for Program 1 has been expanded with two additional sheets in preparation for Program 3. One additional sheet is for attractions that are associated with locations and edges by their labels, so each entry on this sheet includes an attraction label in column 1, a location or edge label in column 2, a brief description of the attraction in column 3, and comma separated thematic keywords in column 4. The thematic keywords can be in any order, but each keyword must correspond exactly to a theme label given on a second additional sheet on themes. In program 3 we will be expanding upon our treatment of utilities, constraints and optimization, supervised learning, deep learning, and in Program 4 still farther (e.g., knowledge graphs).

Each individual will add at least 3 new attractions and the necessary location and edge labels, as well as thematic keywords. Optionally, all students can add theme labels if they feel so inspired. Thematic content of road trips can vary, such as Civil Rights, Diners Drive-ins and Dives, Civil War, LBGTQ, Nature, Native American Sites, Universities, and lots of others.

In each additional sheet there is a column that asks you to identify yourself as the one who made entries. For purposes of this identification you are each associated with an individual identifier (on Brightspace), id1 through id32. These will remain your identifiers for all programs, and they aren’t in alphabetical order. Just give your id number in this column.

Many of you were associated with a group of two or three for Project 1. You will be able to change groups after each program if you wish, including making a choice to work alone. Please let Kyle and I know asap whether you wish to change, including being added to a group or more than one. In part, the reason for this is that while the first program is well prescribed, later programs will allow you to exercise creativity on process and on content.

The possibility of changing groups after each program seemingly complicates latter software development, but you are allowed to take your previous team’s software with you to your next group (including alone), and potentially build on that, while acknowledging your previous team.

Guidelines on AI: You may use generative AI to help specify, design, implement, document, and evaluate your programs. In fact I encourage it. You can post openly on Piazza about ideas and designs for each program, but do not post code (though you can post prompts) unless Kyle and I approve it.

The default programming language for the programs is Python, though if you really want to use a different language then make a pitch to Kyle and I.

—————————— End of Program 2 specification ——————————–

Back to CS 4260/5260 main page.

Programming Project 1

Part A) You will create an anytime variant of A* search that identifies routes (road trips) on a road network from a specified start location to a specified goal location. In creating an anytime variant of A* you will have to think about how reentrancies (i.e., multiple partial paths to the same location) should be handled.

For this project a road network has the following format.

A location is represented by latitude and longitude coordinates, and a name or label.

location_label  latitude   longitude

An edge is represented by a label, the two locations that the edge connects,  label A and label B, and an actual (on the ground) distance in miles between A to B (i.e., a weighted, undirected edge).

edge_label   location_label_A    location_label_B     actual_distance

For example, the following might be given in a road network (two files, one for locations and one for edges):

Location Label       Latitude      Longitude

NashvilleTN         36.174465    -86.767960

MemphisTN         35.117500    -89.971107

JacksonTN           35.614517    -88.813947

 

                       Edge Label                             Location1         Location2      Distance

Nashville_tofrom_Memphis_on_I40    NashvilleTN   MemphisTN       212

Nashville_tofrom_Jackson_on_I40      NashvilleTN   JacksonTN         129

Jackson_tofrom_Memphis_on_I40      JacksonTN     MemphisTN       88

The actual_distances are edge costs in the graph of cities. They are actual driving (or walking) distances, and are not straight-line, as-the-crow-flies distances. Note that the Nashville to Memphis edge is crossed out, because we will limit ourselves to edges between 50 miles and 200 miles, inclusive.

The top-level interface to the functions you will write will be

RoadTrip (startLoc, goalLoc, LocFile, EdgeFile, resultFile)

A solution will be written to the screen and the resultFile, using the same format for both cases. Each solution path is identified by a unique program generated solutionLabel. The user will then be asked whether another solution should be returned. If ‘yes’, then the anytime search continues. These steps can occur indefinitely until the user answers ‘no’, or the Frontier is empty, at which time the search terminates and returns a summary of its run, including

(a) the size of the Frontier at termination,

(b) the minimum, mean, and maximum costs of solution paths that were found,

(c) the solutionLabel of the minimum cost path found,

(d) a list of locations that were visited (checked for goalness) across the entirety of the anytime search (with duplicates removed).

(e) the instrumented runtime of all continuations of A* search (that is, do not include the time that search is paused between solutions so that you can answer yes/no).

This summary will be written to screen and to the resultFile immediately following the last solution returned for a given start/goal location pair. Note that there is a separate resultFile for each start/goal location problem.

Each solution path is essentially a sequence of edges that connect the start location and the goal location, with auxiliary information, formatted as follows, where interLoc_i is the location label for an intermediate location, between start and goal, of the path:

solutionLabel   startLoc   hCost   //hCost is estimated distance to goal
1. startLoc   interLoc₁   hCost   edgeLabel   edgeCost   gCost   fCost
2. interLoc₁ interLoc₂   hCost   edgeLabel   edgeCost   gCost   fCost
…
N-1. interLoc_N-1 goalLoc 0         edgeLabel   edgeCost   gCost   gCost
goalLoc   gCost                       //gCost is total path distance

Each solution path is followed by a new blank line.

Each line, except the first and last, corresponds to an edge between two locations with those labels given first and second on the line, followed by the hCost of the second of these locations, followed by the actual edge cost between the points (as given in the data), followed by the gCost so far (i.e., the cumulative cost), followed by the fCost of the path so far, which will equal the sum of the gCost and hCost given on the same line.

Importantly, while the data provides undirected edges each line of a solution gives a directed edge, in which the direction is from first location to the second location in the line of output. So your program will have to revise (or reinterpret) the undirected edges to be directed edges as appropriate. This shouldn’t be difficult.

Note that while edge costs are given in the data for edges, the hCosts are not given, but these will have to be computed from the coordinates of locations, one of which will be the goal location.

Part B) A Google doc includes locations and edges. Each individual will add at least 3 new locations and the necessary edges to connect each of your locations to an existing location. Locations should correspond to cities and towns. Each edge cost should accurately reflect driving distances and each edge should be between 50 and 200 miles (if you really want to include a city/town with edges to others that are less than 50 miles, then ask).

All programs, regardless of team, will be evaluated on the collective graph, downloaded as two csv files of locations and edges.

The final column of each sheet in the Google spreadsheet asks you to identify yourself as the one who added locations and edges. For purposes of this identification you are each associated with an individual Program 1 identifier (on Brightspace), id1 through id32. These will remain your identifiers for all programs, and they aren’t in alphabetical order. Just give your id number in this column.

Many of you are also associated with a group of two or three for Project 1. Everyone who posted a preference on Brightspace is associated with a group (except one whose response I could not read – an odd filetype). I want the rest of you to explicitly post a preference for teammates, or for working alone, or for working with others but you don’t have a preference as to who. I’ll make final assignments by Monday (but I won’t change teammates for any existing group).

You will be able to change groups after each program, including making a choice to work alone at some point. That is, each program has its own group assignments though I expect that in most cases you will want your group to stay the same and I’ll respect that. In part, the reason for this is that while the first program is well prescribed, later programs will allow you to exercise creativity on process and on content. In subsequent assignments you will further develop a road trip recommender system, and include other data with locations and edges, such as descriptions of attractions, history and personal stories of locations and edges through time, sports, seasonal temperatures — basically the possibilities are (nearly) endless. Thematic content of road trips can vary, such as Civil Rights, Diners Drive-ins and Dives, Civil War, LBGTQ, Nature, Native American Sites, Universities. Finally, you will be making choices on computational processes, including between machine learning and search methods, and knowledge representations. You may get so far as to gamify your system.

The possibility of changing groups after each program seemingly complicates latter software development, but you are allowed to take your previous team’s software with you to your next group (including alone), and potentially build on that, while acknowledging your previous team.

Guidelines on AI: You may use generative AI to help specify, design, implement, document, and evaluate your programs. In fact I encourage it. You can post openly on Piazza about ideas and designs for each program, but do not post code (though you can post prompts) unless Kyle and I approve it (e.g., you might instrument your code to measure runtime which you believe would help others).

The default programming language for the programs is Python, though if you really want to use a different language then make a pitch to Kyle and I.

Deliverables: You will be submitting (a) a fully documented program listing, (b) a summary and reflection on the use of AI in all aspects of the assignment, (c) resultFiles for at least 3 test runs (i.e., 3 anytime searches of at least three continuances each).

Back to CS 4260/5260 main page.