Chained A* algorithm

  • 7 Replies
  • 760 Views
*

Marcus Vilain

  • Roomba
  • *
  • 8
Chained A* algorithm
« on: February 27, 2018, 06:28:17 pm »
Hi all,
Not sure it's the right place for this very first question but here it is :
Suppose i'm solving a problem using the A* algorithm (let's call it A1)
Suppose now, that for each successor s of a node n, I need to start another A* algorithm (let's call it A2)
How the cost c returned by A2 must be used to correctly guide the search in A1 ? Is it the g cost of A1, the h cost of A1 ? a part of g or h ?
Thanks,
Marcus

*

infurl

  • Trusty Member
  • ********
  • Replicant
  • *
  • 612
  • Humans will disappoint you.
    • Home Page
Re: Chained A* algorithm
« Reply #1 on: February 27, 2018, 09:12:04 pm »
What's the application that you are working on? Homework? Computer game? World domination?

The defining characteristic of the A* heuristic is that it must consistently underestimate the remaining cost in order to converge on a solution. It sounds like you are describing the iteratively deepening search variant (the others being breadth-first and depth-first search) but the heuristic remains the same.

*

Marcus Vilain

  • Roomba
  • *
  • 8
Re: Chained A* algorithm
« Reply #2 on: February 27, 2018, 09:52:00 pm »
Hi,

I work on a planification problem:
Tasks are to be done. A1 tries to affect these tasks to computers.

Thus, a node in A1 represents a possible affectation (or not...  At this step we only make assumptions).

Then, this possibly feasible affectation is submitted to A2.

The most important fact is that we try to call A2 the less possible.

Thank you







Envoyé de mon iPhone en utilisant Tapatalk

*

infurl

  • Trusty Member
  • ********
  • Replicant
  • *
  • 612
  • Humans will disappoint you.
    • Home Page
Re: Chained A* algorithm
« Reply #3 on: February 27, 2018, 10:39:48 pm »
That sounds like very interesting work. By "affect" do you mean "assign" or have I misunderstood you?

A generic planning algorithm such as A* might not be the best way to tackle what sounds like a scheduling problem. If scheduling is dynamic then there are a number of well documented approaches employed in multi-tasking operating systems that ought to scale up to distributed systems. Alternatively, if tasks are well defined and scheduling can be calculated ahead of time then maybe the Simplex algorithm would be more applicable.

*

Marcus Vilain

  • Roomba
  • *
  • 8
Re: Chained A* algorithm
« Reply #4 on: February 27, 2018, 11:13:21 pm »
You’re right. «affectation » means « assignation ».

The fact is that for now, the potential affectations are done by a CSP solver.

Only a subset of theses potential affectations are submitted to A2.

The question is : to be homogeneous, can this CSP be replaced by a A* algorithm (but from you previous post, it seems that this is maybe not a so good idea...) ? If so, how the cost computed by A2 can be used in A1 ?

Marcus






A1 is not a A* but a CSP

*

infurl

  • Trusty Member
  • ********
  • Replicant
  • *
  • 612
  • Humans will disappoint you.
    • Home Page
Re: Chained A* algorithm
« Reply #5 on: February 27, 2018, 11:45:57 pm »
Constraint Satisfaction Problems are the more general case. Searching a problem space is just one kind of algorithm that may be used to solve a CSP. As far as achieving homogeneity is concerned, if the problem can be solved by searching a problem space then you can do it using an iteratively deepening A* search. That will combine all your searches into one homogeneous solution.

However you stated the problem was one of assigning tasks to computers, so that's a scheduling or resource allocation problem which would be handled differently. If you already know what tasks have to be performed then you don't need search, you need a different kind of CSP algorithm such as bin-packing or resource levelling. Consider the following questions.

Do the tasks have dependencies?
i.e. Does Task X have to be completed before Task Y can start?

Are the resources (computers) specialised?
i.e. Can some tasks only be performed by some computers?
You might have to use resource-levelling.

Do the tasks take a predictable or an unpredictable amount of time?
If the former then you can pre-calculate an optimal solution using Simplex.
If the latter then you will have to use a dynamic scheduling algorithm.


*

Marcus Vilain

  • Roomba
  • *
  • 8
Re: Chained A* algorithm
« Reply #6 on: February 28, 2018, 12:25:00 am »
Yes, tasks have logical dependencies ( task a if and only if task b) and temporal (before, after, starts at the same time ... )

Computers are specialized (a task can be made more or less efficiently/quickly by a computer). A computer cannot make some tasks)

To get the whole picture, see these computers as embedded in robots that need to be at certain places to full fill each task.

Don’t know enough about IDA*, I need to take a look... tomorrow !

Thanks



*

spydaz

  • Trusty Member
  • *******
  • Starship Trooper
  • *
  • 305
  • Developing Conversational AI (Natural Language/ML)
    • SpydazWeb
Re: Chained A* algorithm
« Reply #7 on: April 09, 2018, 04:31:12 pm »
Hi all,
Not sure it's the right place for this very first question but here it is :
Suppose i'm solving a problem using the A* algorithm (let's call it A1)
Suppose now, that for each successor s of a node n, I need to start another A* algorithm (let's call it A2)
How the cost c returned by A2 must be used to correctly guide the search in A1 ? Is it the g cost of A1, the h cost of A1 ? a part of g or h ?
Thanks,
Marcus


This is a recursive algorithm!

You need to explain it clearly so the algorithm can be defined properly;

Recursive algorithms are solved with Do while/Until loops using your if / then logic to test for the Condition.using a function to call itself.
[/font]

 


Something crazy is happening to me with my work
by ranch vermin (General Hardware Talk)
Today at 06:17:29 am
XKCD Comic : Dark Matter Candidates
by Tyler (XKCD Comic)
August 20, 2018, 12:00:55 pm
outline from gadient mask
by yotamarker (General AI Discussion)
August 19, 2018, 03:09:03 pm
absolutely nothing motor controller
by ranch vermin (Home Made Robots)
August 19, 2018, 11:49:42 am
Friday Funny
by LOCKSUIT (General Chat)
August 17, 2018, 04:10:47 pm
Ten Commandments of Logic
by RoyMac (General Chat)
August 17, 2018, 12:01:02 pm
XKCD Comic : Equations
by Tyler (XKCD Comic)
August 17, 2018, 12:00:14 pm
XKCD Comic : Repair or Replace
by Tyler (XKCD Comic)
August 16, 2018, 12:01:05 pm

Users Online

71 Guests, 0 Users

Most Online Today: 86. Most Online Ever: 208 (August 27, 2008, 09:36:30 am)

Articles