CS105/CS360/SE360 Artificial Intelligence
Pentagons Formation using Tangram Pieces
Tangram is one of the most popular games to play with. You put figures of 7 pieces together (five triangles, one square and one parallelogram). You must use all pieces. They must touch but not overlap.
There are 32 half squares or 16 squares altogether.
Copyright By PowCoder代写 加微信 powcoder
We could take the half-squared triangle as the basic form, because each square built for all seven tangram pieces has the simple length (perimeter) of 4 units.
There are many convex and non-convex figures/shapes of pentagons that you can build from all the 7 tangram pieces. Some of them are given below.
In this project, you are required to use AI search methods (uninformed search methods such as Breadth First search, Depth First search, Iterative Deepening and Uniform Cost search) and (Informed or heuristic search methods such as Greedy search, A* algorithm and Iterative Deepening version of A* : IDA*) to perform pattern matching, recognition and pentagons formation. For some figures with the same look, there are more than one ways to form it. Your jobs are given as follows:
1. Try to form all the possible distinct pentagons (convex and non-convex) from all these 7 pieces.
2. For some figures, find all the possible ways to form them, e.g., an above convex pentagon has 4
ways to form it.
All seven tangram pieces consist of many half squares(triangles), each with this shape:
3. Setup important problem formulation that is most suitable/useful for solving this problem.
4. Use at least TWO uninformed and at least TWO informed search methods to solve this problem.
5. Implement these search methods in a computer system so that all the 7 pieces could be used to
form all distinct convex and non-convex pentagons. Bonus will be given to team(s) who could
give/find all the possible ways to form same figures.
6. Analyze the properties of these search methods in terms of completeness, optimality, time
complexity and space complexity when solving this problem.
7. You are required to form teams yourself. Each team should have 3 or 4 students. You are advised
to include in your team at least ONE student who knows how to do programming, any programming languages, Matlab, Python, R, C, C++ and/or Java etc. could be used.
Submit to me student names, ID and course, class of your team members in week 4 in the class session. Students forming a team should come from the same course (e.g., CS360, SE360 or CS105) and same class (e.g., D1 or D2).
A user friendly interface should be provided. A system name/title is given, e.g., “A Pattern Matching, Recognition, and Pentagons Formation System”. The system should have options such as pull-down menu of convex or non-convex figures, pull-down menu of different search methods, etc. for user to choose from and execute. The results are displayed on the screen.
10. Each team is required to submit a report which includes the introduction, detailed description of your problem formulation, number of goal states (Pentagons) you could reach, get or form, problems you have solved, your contributions, what you have achieved in your system.
11. A clear, succinct, easy to understand user manual/guide on how to INSTALL and EXECUTE the software (freeware or others) and your DEVELOPED system should be included in the report.
12. You are also required to submit a full and detailed report including the following information.
All your team members’ name, ID number and team number (assigned in the week 12),
Course (e.g., CS360, SE360 or CS105) and Class (e.g., D1 or D2).
The problems you have solved.
Which uninformed or informed search methods you have used, how and why?
What evaluation function you have used to guide you in branching (expanding) nodes?
How and why such functions or changes are introduced? What are the reasons behind
introducing such changes?
Figures or diagrams showing the problem formulation of your system should be included.
A comparison of properties of different adopted or implemented search methods in terms
of Completeness, Optimality, Time and Space complexity need to be done and included.
The results you have obtained. Different figures showing results, many goal states, etc.
13. You are required to submit in the last/final class session (Presentation Session(s) held in week 14 and/or week 15) your Hardcopy report and a USB which contains the source codes of your developed system, shareware and/or freeware used, user manual/guide on how to INSTALL and EXECUTE your system, and your FULL report mentioned in points 10 — 12.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com