4
$\begingroup$

I understand A* and Dijkstra for avoiding obstacles, they require that points are traversable there are points that are not traversable thus the algorithms wont bump into the obstacles because the obstacles cant be traversed or maybe if cost is a factor the relationships between the point is of such a high weight that the algos wont take that path. ive been using graphs this way with good results so A* and Dijkstra are great candidates and I have them working sweet, but they always require me to have points in place to traverse, im the one who puts the points in and creates the relationships between the points, its not ai or any type of learning, its just an algo traversing points on a map.

Lets say I have a white image, a green blob in the middle and points at either side of the blob, I need to get from a -> b I don't have points to traverse I just have this image, is it a case of machine learning to learn an agent to get from point a -> b then apply that learning to more complex maps? if so what what should I be looking at? or is that the wrong route to take pardon the pun. If any of my google queries contain "ai" all I get back is deep mind this and deep mind that and a lot of game developer answers that include sending rays out in front etc, but again that's not ai or learning.


Edit after answers were posted:

Ok thanks for the responses, I don't have 50 reputation so I cant answer to your posts Both answers seem to come back to graphs though as well as the paper referenced in the first answer which is what im using just now. Ok so Images is definitely out as your right its a super amount of work and would be very complicated. Ill try and explain it in a different way, take this image of a route created by my graph, the route is fine, it adheres to directional traffic separation schemes and is perfectly usable, zoomed out it looks a bit jaggy but zoomed in the route is fine enter image description here

Are you saying there is no way an agent could be trained to navigate around a map going from a -> b without the use of graphs? In the image above the underlying dataset takes into account ocean points (low resolution), areas where there are many island (high resolution), canals, tss, port approaches and harbour navigation etc so there is a lot of under lying data and your route is only as good as the data you put in, theres also a lot of other concerns especially in the ocean portions where you don't wants to just connect to your neighbour, you want your route to take longer jumps.

If you had an array 640 millions point for latitude longitude 3 decimal precision with high values for land and low values for water, could an agent be trained to go from a -> b? by keeping the agent on water and if it crashes into land then do the simulation again but learn from its mistakes?

I know its a long shot but im just trying to get a handle on whats being done or if there is anything out there to look at.

Great responses thanks.

$\endgroup$
0
$\begingroup$

Lets say I have a white image, a green blob in the middle and points at either side of the blob, I need to get from a -> b I don't have points to traverse I just have this image

If your image is as "simple" as you describe here, with very easily distinguishable colours, the easiest solution would likely be to construct a graph as expected by algorithms such as A* as follows:

  • Every pixel becomes a node in the graph, with connections to all adjacent pixels
  • Green pixels (the green blob in the middle) are marked as non-traversable (or simply don't have connections to adjacent pixels) (I assume this thing is your obstacle).
  • Pixels belonging to the points on either side of the obstacle are marked as starting and goal vertices.

Then, you have the graph that a traditional pathfinding algorithm like A* would expect, and can simply run the algorithm there.


If you get less "clear" images (i.e. not brightly coloured, easily distinguishable things, but more like real-life top-down images of an area), then the above won't really work anymore. In such cases, you'd likely want to look into Reinforcement Learning approaches, where you give an agent a reward when it successfully manages to find a connection between start and goal. In particular, you'd need Deep Reinforcement Learning approaches, because otherwise you're not going to be able to handle complex images.

Note that these approaches are not going to be simple to implement or immediately understand for 100% if you're a beginner. There won't be any "beginner-friendly" approaches for the problem you describe, it simply is quite a complex problem (requiring a mix of "decision-making" and "understanding" images).

$\endgroup$
-1
$\begingroup$

Getting from a position we label $a$ to some point we expect to exist we label $b$ is one of the basic capabilities we need from intelligent systems. It is not as intelligent as, for instance, developing a business plan, but it does involve planning, often the use of a map, recognition of landmarks if the path has been traversed or partly traversed before, and avoidance of an accident.

For an automated vehicle, avoiding objects can be synonymous with saving lives. For an automated lawnmower, avoiding objects is not quite as high risk but still key to the safe mowing of the lawn. Obstacle and pedestrian avoidance is important. It may be an operation carried out a thousand times a microsecond by computers in consumer products used globally just a few decades from this writing.

Route Planning, Obstacle Avoidance, and Map Maintenance

A* and Dijkstra are not obstacle avoidance algorithms. They are route planning algorithms.

They do, however, require that edges connecting vertices are traversable. They do not process nontraversability of edges. All edges are traversable because none are built through obstructions.

The cost in these strategies is related to time and distance, not risk of accident, so the aversion is to long or slow paths through the graph of vertices and edges that represents the transportation option map.

They always require me to have points in place to traverse.

Yes, the vertices and edges are not discovered as a part of A* or Dijkstra. The existence of a map is assumed, and the visual and auditory ques that humans would use to mow a lawn, route a train, fly a plane, or drive a truck or car are not connected to algorithmic choices.

The awareness, which we can consider a repeatedly updated milestone in planning, sought in the question is, when seeking a path $a \Rightarrow b$, can we maintain a directed graph based on visual (and perhaps auditory) queues? This is a step toward the important AI goal of corroborating map information with real time ascertainable immediate environment. It is also a step toward real time collaboration between autonomous vehicles to maintain a globally shared map.

The maintaining of a map is required in automated driving to cope with when a street or lane is closed and it is one possible way to deal with foot traffic. In automated vacuum cleaning, map maintenance is required to deal with both foot traffic, toys or clothes on the floor, or re-positioned furnishings.

Building a Map from Scratch

The specific system envisioned in the question is an image where a blob can be distinguished in an image when the camera is pointed at $b$ from $a$, assuming we at least have the coordinates of $b$ relative to $a$ so we can point the camera toward it. Can we teach a network to construct the points or array of points that allows passage around the blob at a safe clearance distance?

Yes, but we may not need to. Assuming that as the vehicle or robot moves it will reevaluate, we can determine which side to aim toward based on which angle of approach is closest to the angle of $b$. Unless we know something about what may be after the blob, that will always be most likely shortest path. However, the blob may have a sign in front of it with an arrow pointing left. That is where convolution methods and other machine learning techniques can plan an important role.

Reductionism Probably Not Applicable

The broader question asked is whether one can "[teach a network] to get from point $a$ to point $b$ is another possible application for an architecture of transportation automation that includes artificial learning networks.

However, a reductionist strategy is not the best for chaotic systems. It is not from learning simple maps that complex maps can be maintained or utilized well, it is from learning complex maps. In other words, with most of the current machine learning approaches, we do not teach the machine like we would a child, simple first.

We want the statistical distribution of permutations in the concept class being learned to be the same between the training examples and the scenarios over which the learned behavior is expected to work.

Web Searches

Web searches are an excellent way to find information today. Searching on the web has replaced many long standing news and information sources, but telling the difference between transient hype and information that is likely to be both pertinent and valid and that it will continue to be a year from now is still an art.

It isn't smart to completely dismiss what the web searches return for a simple list of words that describes what it is we seek. And Google's acquisition of DeepMind and the bright minded game developers may provide partial or complete solutions for the kinds of problems this question asks, but it is wise to diversify our information sources.

We can buy some books, join some discussions, watch some video recorded lectures, refine our searches, and reading some scholarly articles. One key to finding authentic and accurate information is to, as a scientist should, look for corroboration between theory and actual experimental results.

Nonetheless, it was an educated guess at a web search and a few educated guesses for clicks from the returned results that led to this excellent article which outlines the various map usage options for engineers.

Engineering Route Planning Algorithms, Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner, 2009

It does not discuss the construction of maps from scratch, corroboration of maps with visual observations, or the maintenance of map information locally or more globally.

The High Challenge of Real Time Map and Route Adjustment

This array of capabilities is not new. Seeking in robotic devices the ability to find paths without maps, build maps from discovery, and then use them later began with Claude Shannon and his mouse Theseus. It was a maze learning mouse he devised and built in 1952, quite a remarkable achievement since the supercomputers of that time have similar computing power to low end smart phones of today.

Shannon is one of the key people in the development of digital systems, probably the most important of them all. Reading anything he wrote about information theory is not only pertinent to this problem, but also any other problem you are likely to encounter in the development of virtually any type of system today.

Certainly, information theory is key to this problem of automated map-making, map using, and maintaining one already made, all of which require in varying degrees the processing of visual and auditory information in real time. What percentage of these systems will end up falling under the label Artificial Intelligence and what is straightforward applications of engineering formulae is anyone's guess.

But consider the range of products that rely on the development of these transport automation technologies.

  • Buses
  • Parcel pick-up and delivery
  • Mail pick-up and delivery
  • Other road motor vehicles
  • Trains
  • Commercial, private, and military aircraft
  • Vacuum cleaners
  • Lawn mowers, trimmers, and leaf blowers
  • Robots that specialize in doing the laundry
  • Robots that specialize in snow and ice removal
  • Robots that go find things we need right now and put them back later

Buses are distinguished from other vehicles and listed first because they are probably the easiest to automate. Buses have the greatest weekly route consistency and strictest constraints on lane changes.

This last one is the king of map-making and map reading in multiple dimensions and across arbitrary domains. We had hope for dogs, and dogs can have fun fetching things we've thrown. Retrievers have been bred to retrieve fowl we may have shot for dinner, but they don't have the capacity for fetching things we haven't hunted or thrown for them to fetch. In film-making and some business circles, the role has a name: Gofer.

Perhaps robots can be engineered with AI to the point where their breadth of understanding, both on the natural language end and on the side of organizing a map of where things should be or likely are stored. This is still essentially an $a \Rightarrow b$ problem, but with more dimensions of height, which may involve shelf level and closet door sophistication.

We can see that the $a \Rightarrow b$ scenario may be the most important first step toward a great new line of products to improve road safety and conserve resources, including energy and time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.