FIT ČVUT Course Pages
BI-ZUM — Základy umělé inteligence
Jdi na navigaci předmětu

Semester work

Recommended entries

Mickey’s clubhouse

Mickey, Minnie, Daisy, Donald, Goofy and Pluto bought a club. The price of the ball was 20 rainbow balls, and each member could contribute 1 to 8 balls (how many we can imagine). The members always meet on Sunday afternoons and at the same time one of the members has the right to decide on the entertainment that will take place that day, depending on the amount of his share. Our job is to create a schedule of who will ever determine the fun, while respecting a number of restrictions.

  • For example, we want the members of the club to have days of the year evenly according to the seasons, ie that everyone has the opportunity to invent entertainment for summer, winter, etc.
  • Each member can express a preference for days when he wants to have fun according to himself, or whether he wants several consecutive weeks, and days when he does not want to invent anything.
  • Donald forgets a lot and often repeats himself, so we don’t want him to be able to choose the fun many times in a row. Minnie is selfless and still wants to come up with something, but we have to make sure she doesn’t burn out.

Mazes

We have a maze (for example, a grid map) and mazes are placed in it. To do this, we have a group of robots whose task is to collect mazes. Each robot will take only one maze. For simplicity, we can ignore collisions between robots. Somewhere on the map is marked a collection point for mazes.

  • It is possible to solve various variants, for example the positions of mazes are known in advance or not. Robots share information, or about discovered mazes, or not.
  • We would like to collect as many mazes as possible in the shortest possible time. You can compete in the collection with another team of robots.

Lost robot

The question of localization and mapping in robotics has been mentioned only very briefly, but this task will clarify it. We have a familiar environment represented by a map. The map can be two-dimensional or, for interest, three-dimensional. Two-dimensional map si we can present it as a grid from a game (see movingai.com). We have a robot that knows the map and has optical sensors that are accurate but limited in range. So the robot sees its surroundings precisely to a certain distance. We place the robot on beautifully selected place in the environment shown by the map.

  • The task for the robot and for you is to orient yourself in the environment according to the map, ie to determine the place on the map where the robot is located. Of course, there are no marks in the environment, so the robot must orient itself according to the "landscape" it sees, of course it can be very monotonous.
  • Imagine a robot in a corridor system. As a criterion, we can take the time for which the robot’s orientation lasts - the shorter, the better.

Infallible chess player (or rather a checker on a small chessboard)

We will be creating the perfect strategy for small games. The perfect strategy is that if we play by it, whatever the opponent does, he will always lose. For some turn-based games there is, for example for Checkers, when we have the option to draw first.

  • Your task will be to choose some turn-based games and find the perfect strategy for them. This is not easy for games in their full original size, so we will limit ourselves to Checkers or Chess on a small chessboard, for example.
  • We assume that the search for the perfect strategy will take place automatically, ie it will be searched for by one of the discussed algorithms.
  • We welcome other turn-based games, such as Go variants in a small space, various atypical Chess (special pieces), etc.

The 'Guardian' drone in a stalactite cave

We have one flying drone who is very careful and doesn’t want to break the propellers. His task, however, is to fly through a stalactite cave with large and sharp stalactites. Devise and implement a motion planning algorithm such a drone. We have to assume that the drone moves in a very fragmented three-dimensional environment, where it must not hit anywhere, or even get closer to an obstacle. We neglect the sensory side of the task, the drone environment perfectly he knows and always knows his exact position.

  • This is a search for a safe path for a drone, which is not a completely arbitrary path.
  • We can consider two criteria, namely to move along a safe path, but at the same time to reach the destination as quickly as possible.

Cards player with a stone face

Although we did not have games with incomplete information and uncertainty, the basic intuition of how to deal with this problem will suffice for us. We will design a UI for playing card games with bets, such as Poker or others. The advantage of artificial intelligence is that he does not show concern when the bets go up and the cards held are weak.

  • Design various procedures for playing the selected card game with bets, intuitive procedures will suffice. If you manage to integrate some technique from the lecture, the better.
  • Test playing techniques with each other and evaluate what is crucial for successful playing.

Busy beaver

We assume that the students of the course on artificial intelligence know what a Turing machine is. As part of the task, we will want to create a Turing machine that is as small as possible, but will be quite industrious. So it will run as long as possible, but not forever, eventually stops. This task is generally known as Busy Beaver.

  • Use the techniques discussed to create such a Turing machine.
  • It is necessary to set certain input restrictions on the number of states and symbols, while we recommend working with very small numbers, eg: 2, 3, 4.

Five-year planning

An analogy of the previous task, however, in the world of classical planning. Try to create a classic planning problem that will be as small as possible in terms of the length of the assignment, ie in terms of the number of constants, the number of actions, etc., but will generate the longest possible plans. Of course, such a planning task is about as useful as planning a five-year plan in a planned economy, but it shows the complexity of the planning task and the limits of planners.

  • You can try to generate and test the described planning tasks automatically.

Automatic programmer

Many jobs will disappear due to the rise of artificial intelligence, and people will finally be able to focus on what they enjoy (such as playing computer games). Try to help ensure that the Ajt jobs finally disappear and be replaced by AI and the Ajťas were thus able to devote themselves fully to their hobbies. For simplicity, we will come up with a UI that will replace the programmer for simple processors that have say three registers, AX, BX, and CX. The memory will be marked with the Pam field, with Pam [i] means the i-th memory cell. We have several instructions: Load (memory cell Pam [i], register), Save (register, memory cell Pam [i]) with the natural meaning of saving the contents of the memory cell to the register, resp. inserting the contents of the registry into a memory cell. We still have some operations with registers eg: Swap (register1, register2), which swaps the contents of the registers, vector Shift, which takes all registers and performs a rotation resp. shift ie content AX goes to CX, content BX to AX, content CX to BX.

  • Build a program from the above instructions, which swaps in memory two strings whose positions are known in advance. Thus, for example, at the beginning is the content of the memory: "Paul found out that Peter does not know AI, and therefore threw him away from the test." We want to keep in mind the program: "Peter found out that Pavel does not know AI, so he threw him out of the exam."
  • We do not want to compile the program manually, we want to compile it automatically. Therefore, use one of the discussed techniques for this automation.
  • You can generalize a simple processor in various ways, add instructions, registers, etc. You will find out where the limits are similar to programming automation and whether it is possible to actually replace ajťáky with current techniques.

MAPF (read "mep ef")

Multi-agent path finding (MAPF) is a classic planning task in artificial intelligence. An undirected graph is given. There are agents at the tops of the graph so that there is always at most one at the top and the task is to find non-colliding ones the paths by which agents get from their initial peaks to the specified targets. Each agent has its own unique target peak.

  • The task traditionally talks about agents, but they are not agents in the sense in which we discussed them. Here they have no internal intelligence, everything is handled centrally from an external point of view. Previously, the task was more aptly called Cooperative Pathfinding (CPF).
  • Implement a technique that handles path planning for a non-trivial number of agents (eg> 5) in a non-trivial graph (eg a 10x10 grid with an obstacle).
  • The task can also be modeled using classical planning.

BetaGo (or rather GammaGo).

Try to build a competitor for AlphaGo from the discussed techniques (by the way, the role of MAPF and AlphaGo is connected by the same person, namely David Silver, who invented the correct name CPF for the task). It’s about finding a game strategy for the game Go. Basic The approach can be based on classic game algorithms - minimax, alpha-beta. Since the game tree is large, you need to figure out how to estimate the rankings in the nodes of the tree, from where the search can no longer continue.

  • You can compare the power of your design with your own gaming power or with AlphaGo.
  • If you manage to create more variants of the game algorithm, you can try them against each other.

Sudoku at 100%

Consider the well-known SUDOKU filler, where we have to add digits 1 to 9 to a 9x9 grid so that different conditions for the diversity of digits are met. We will not describe the rules in detail, we assume that they are known. Yours the task is to solve the replenisher using artificial intelligence techniques, but so that it is done as quickly and guaranteed as possible, ie the solving algorithm always ends and gives the correct solution.

  • It is possible to use the approach from the CSP, ie to model Sudoku as a CSP and then perform a search over the CSP
  • Or you can use the conversion to propositional fulfillment. An interesting question is to implement more techniques and compare their performance.

Sudokář - klikar

Again SUDOKU, but this time we bet on luck, so the handle. The systematic algorithms from the previous task are not always easy to program, but everyone can handle local search / optimization. We pay for this by the incompleteness of local algorithms, but their simplicity balances it.

  • Formulate SUDOKU as a local search task, ie in the sense of a hill climb algorithm.
  • Try different options to change the solution candidate locally and compare them.
  • The 9x9 array is a breeze for today’s computers (of course, as ever), so try the generalized SUDOKU on a larger board.

Masters steering wheel

The automobile, ie the autonomous one, is a classic case of a robot. We will try to plan the movement when parking - it is transverse for amateurs, we will park longitudinally in a row into the gap, which is just right. Slightly newer cars feature automatic parking they have, so give it a try if you can at least know what car programmers have already done. For simplicity, we omit the sensory side, the control algorithm sees everything exactly.

  • Cars can be further considered as rectangles. The car can drive forwards and backwards. The steering is by means of the front wheels, when turning the wheels the car rotates, so it travels in a circle with the center at the intersection of the axis of the rear axle and the axles of the front wheels, which means, among other things, that each from the front wheels it must be turned slightly differently (inner more).
  • Use the knowledge of forward and backward kinematics, you can discretize the environment appropriately.

Cottage motoring

Again, autonomous motoring, this time cottage, ie with an attached and nicely loaded cart / cart. We will back up and pack, here the variant of transverse parking (behind) is already interesting. We are also interested in longitudinal packing. Again, some cars have an automatic parking function with a wheelchair, so you can test whether the carmaker would care about you at all.

  • The same simplifications apply as in the previous task, ie we neglect the sensory side, the algorithm sees everything.
  • The task is to plan the movement again, which will successfully clean the car even with a cart and some small space.

Masters of two steering wheels

Some modern cars have the option of turning the wheel on the rear axle. Think about what it can be good for and take advantage of it. For example, for maneuvering in narrow aisles, the ability to steer the rear axle may be useful. Suggest motion planning for such a controlled car.

  • It is important that when turning the rear wheels, the car travels in a circle that is not on the axis of the rear axle, but more in front.
  • You can try motion planning for longitudinal parking or passing through a narrow right turn.

Golden 80s: Pacman

Let’s look at the classic arcade game Pacman in terms of game theory. How to plan the movement of Pacman or the movement of ghosts, provided that the opponent is very intelligent, that is in the case of Pacman, we try to eat as many balls as possible without Pacman being caught by a ghost, in terms of ghosts, we try to catch Pacman as quickly as possible.

  • Design and implement an algorithm for finding game strategies for Pacman and ghosts
  • You may consider expanding, where Blinky (the red ghost) is the commander and controls the other ghosts, as soon as Pacman eats him, the ghosts temporarily (until Blinky revives) stop playing intelligently.

2020s: Multi-Pacman

We will be planning for more Pacmans at once. There is only one Pacman in the original game from 1980, after a few decades we will afford more Pacmans, or multi-Pacmans (after all, unlike 1980, we now have multi-core processors) this brings with it a new rule, namely that only one Pacman can fit on one square of the playing field. Therefore, if we automatically plan the movement of the Pacmans, it is necessary not only to try to eat all the balls, but also to make sure that the Pacmans did not crash.

  • Design and implement a search algorithm for controlling Pacmans
  • You can assume that the ghosts are not very intelligent, they move randomly, near Pacman hungrily

8-bit Games Stike Back: Snake

Design intelligent snake control in the game of the same name Snake. In the simplest variant, it is a square snake, which moves along a two-dimensional grid in a serpentine style, ie the body gradually follows the head, and tries to eat edible squares that are spaced differently in the grid, or new ones may appear. After eating the edible square, the snake lengthens by one square. But we must be careful that the snake does not become entangled in itself.

  • Understand the snake as an intelligent agent in a virtual environment, so its management will be implemented by an agent function
  • Assess the various levels of agent skills that may be useful to you: reflex agent, environment model agent, target agent, etc.
  • Implement an agent function using the techniques discussed, offers: heuristic search, classical planning, various evolutionary techniques

Accountant counts sine

Consider an accountant who wants to calculate a sine. Let’s leave aside why she should do so, but she may need to be educated in trigonometry (during working hours). However, it only has an accounting calculator with numbers and buttons "", "-", "*", "/" and some others, with "" being three times larger than the other buttons. The big plus probably won’t help and overall it looks like a pretty precarious situation, your task is to help. So try to find an expression that will be approximate the sine function at least over the interval (-10pi, + 10pi) with the highest possible accuracy (choose and justify the measurement technique).

  • Allowed operations are: addition, subtraction, multiplication, division, ie what the accounting calculator has.
  • Prefer short expressions, we want the accountant to work and not spend all the working time pressing the buttons on the calculator.

SAT Solver Killer

Propositional Satisfaction (SAT) is a strong target formalism for modeling and problem solving. This is thanks to efficient programs-solvers for SAT. In this task, we torment the SAT solver. Find a short propositional formula in the CNF that is as difficult as possible for the SAT solver (measure the difficulty as the running time or as the number of steps of the solver).

  • It is advisable to set some limits on the size of the formula, eg: the total number of literals occurring in the whole formula will be a maximum of 1000.
  • The recommended solver is link: http: //www.labri.fr/perso/lsimon/glucose/ [Glucose], which is not the most powerful, but gives stable results. Alternatively, you can also look at the competition website link: https://www.satcompetition.org/ [SAT Competition], where other solvers are available.
  • Experience how the results turn out for a satisfiable and unsatisfiable case. Typically heavier not an impossible variant. Try to limit yourself only to satisfiable formulas, or only to unsatisfiable, resp. both.

OCR (Optical Character Recognition) easily and quickly

Let’s have some alphabet characters like images, such as 16x16 grayscale. Your task is to find the position of a few pixels so that it is possible according to the values These pixels distinguish the characters of the alphabet from each other. For an alphabet of 26 characters with black and white images, 5 pixels should theoretically suffice, as the values ​​in these pixels can acquire a total of 2 <sup> 5 </sup> = 32 different combinations which is more than 26.

  • Try to solve the problem for the Latin alphabet, you can find images of characters in the following archive: link: https: //courses.fit.cvut.cz/BI-ZUM/media/labs/dataset.zip [Dataset - Latin].
  • Find as few points as possible, according to which you are able to recognize the characters of one of the Japanese alphabets, namely hiragana, we provide images of the characters in the following archive: link: https: //courses.fit.cvut.cz/BI-ZUM/media/labs /written_hiragana_dataset.zip[Data set - hiragana] (link to zdroj).

Custom theme

If you have an interesting task in the field of artificial intelligence, which you would like to develop, it is possible to submit it as a semester work. The topic does not have to be taught or practiced in the subject, however, its complexity should correspond to the recommended assignment. The difficulty will be assessed by the instructor and the topic will either be approved or some changes recommended. Unapproved topic cannot be submitted.

Topic from the lab

The student can choose some of the topics presented in the HW laboratory. For these options, you can borrow one of the available HW from the laboratory. These assignments are also subject to the approval of the instructor (especially the specification of the topic and scope).